Given an array A of positive integers (not necessarily distinct), return the lexicographically largest permutation that is smaller than A, that can be made with one swap (A swap exchanges the positions of two numbers A[i] and A[j]). If it cannot be done, then return the same array.
Example 1:
Input: [3,2,1] Output: [3,1,2] Explanation: Swapping 2 and 1.Example 2:
Input: [1,1,5] Output: [1,1,5] Explanation: This is already the smallest permutation.Example 3:
Input: [1,9,4,6,7] Output: [1,7,4,6,9] Explanation: Swapping 9 and 7.Example 4:
Input: [3,1,1,3] Output: [1,3,1,3] Explanation: Swapping 1 and 3.
Note:
1 <= A.length <= 100001 <= A[i] <= 10000题目大意：
给出一个数组找出这个数组，在只交换一组数的情况下，求解出第一个比当前小的排列组合。
解题思路：
从后向前遍历整个数组，找出第一个有上升趋势的数，这个数字是目标位置，那么它需要与谁进行交换？
再次从后向前，第一个比当前数小的数。两者交换。
class Solution { public: vector<int> prevPermOpt1(vector<int>& A) { int idx = A.size(); for(int i=A.size()-1;i>=1;i--){ if(A[i]>=A[i-1]){ continue; }else{ idx = i-1; break; } } if(idx == A.size()) return A; for(int i = A.size()-1; i>idx ;i--){ if(A[i]<A[idx]){ int cc = A[i]; A[i] =A[idx]; A[idx] = cc; break; } } return A; } };
