题目描述
给你一个正整数的数组 A（其中的元素不一定完全不同），请你返回可在 一次交换（交换两数字 A[i] 和 A[j] 的位置）后得到的、按字典序排列小于 A 的最大可能排列。
如果无法这么操作，就请返回原数组。
示例1
输入： [3,2,1] 输出： [3,1,2] 解释： 交换 2 和 1
示例2
输入： [1,1,5] 输出： [1,1,5] 解释： 这已经是最小排列
示例3
输入： [1,9,4,6,7 ]输出： [1,7,4,6,9] 解释： 交换 9 和 7
示例4
输入： [3,1,1,3] 输出： [1,3,1,3] 解释： 交换 1 和 3
提示
- 1 <= A.length <= 10000
- 1 <= A[i] <= 10000
题解
这题主要出发点有以下几点：
- 首先要求交换后的字典序变小，那么一定要大的和小的交换，并且大的在前。
- 其次要求交换后的字典序尽量大，那么在满足第一点的情况下，大的元素要尽量靠后。
- 最后小的元素要尽量大，并且靠左。
满足这几点条件，也就是要从最右边开始往左寻找，找到第一个上升的数字 A[i]（从左往右看是下降，即 A[i] > A[i+1]）。这一点只为了保证上面的条件1，也就是 A[i] 右边存在比它小的元素。
然后在 A[i+1] 到 A[n-1] 之间所有比 A[i] 小的数字中找最大的那个就行了。如果最大的有多个相同的，取最左边的一个。
因为 A[i+1] 到 A[n-1] 子数组是单调递增的，所以不用全部遍历一遍，只需要从最右边开始往左找到第一个比 A[i] 小的数就行了。然后从这个数开始，继续往左找和它相等的数，直到最左边一个相等的数 ，就是答案了。
代码
class Solution { public: vector<int> prevPermOpt1(vector<int>& A) { int n = A.size(); for (int i = n-2; i >= 0; --i) { if (A[i] > A[i+1]) { for (int j = n-1; j > i; --j) { if (A[j] < A[i]) { for (int k = j; k >= i; --k) { if (A[k] != A[j]) { swap(A[i], A[k+1]); break; } } break; } } break; } } return A; } };
后记
最后不管是用时还是空间消耗都超越了100%的用户：
