LeetCode 1053. 交换一次的先前排列
本帖最后由 798236606 于 2020-3-5 10:10 编辑传送门：https://leetcode-cn.com/problems/previous-permutation-with-one-swap/
分析：
1.交换的两个数必然是前大后小，这样才能产生字典序更小的序列
2.被选择的大数越往后越好，因为越往后对字典序的下降影响越小
3.被选择的小数越大越好（相同值取最左），对字典序下降影响小
4.大数与小数必须先固定一方，由于大数靠前影响大，先固定大数
思路：
1.从后往前遍历每一数，若在这个数之后有比它小的数，它就成为大数固定下来。
2.从大数后遍历每一数，若这个数是小于大数的最大数，它就成为小数固定下来。
3.大小数交换， 得答案。
class Solution {
public:
vector<int> prevPermOpt1(vector<int>& A) {
int n = A.size();
for (int i = n - 2; i >= 0; --i)
{
int maxid = -1, maxn = -1;
for (int j = i + 1; j < n; ++j)
if (A > A && maxn < A)
{
maxid = j;
maxn = A;
}
if (maxid == -1) continue;
swap(A, A);
break;
}
return A;
}
};
页:
[1]