LeetCode 1053. 交换一次的先前排列

798236606

传送门：https://leetcode-cn.com/problems ... tion-with-one-swap/

分析：
1.交换的两个数必然是前大后小，这样才能产生字典序更小的序列
2.被选择的大数越往后越好，因为越往后对字典序的下降影响越小
3.被选择的小数越大越好（相同值取最左），对字典序下降影响小
4.大数与小数必须先固定一方，由于大数靠前影响大，先固定大数

思路：
1.从后往前遍历每一数，若在这个数之后有比它小的数，它就成为大数固定下来。
2.从大数后遍历每一数，若这个数是小于大数的最大数，它就成为小数固定下来。
3.大小数交换， 得答案。

1. class Solution {
   
2. public:
   
3.     vector<int> prevPermOpt1(vector<int>& A) {
   
4.         int n = A.size();
   
5. 
   
6.         for (int i = n - 2; i >= 0; --i)
   
7.         {
   
8.             int maxid = -1, maxn = -1;
   
9. 
   
10.             for (int j = i + 1; j < n; ++j)
    
11.                 if (A[i] > A[j] && maxn < A[j])
    
12.                 {
    
13.                     maxid = j;
    
14.                     maxn = A[j];
    
15.                 }
    
16. 
    
17.             if (maxid == -1) continue;
    
18. 
    
19.             swap(A[i], A[maxid]);
    
20.             break;
    
21.         }
    
22. 
    
23.         return A;
    
24.     }
    
25. };

复制代码