[下一个排列]leetcode556：下一个更大元素 III(medium)

题目：

题解：

思路：两遍扫描

• 思路类比31. 下一个排列，将 n 转换为字符数组，然后求字符数组的下一个更大的排列即可。当不存在下一个排列时返回 -1。

代码如下：

class Solution {
public:
    int nextGreaterElement(int n) {
        string a=to_string(n);
        int i=a.size()-2;
        // 第一遍从后之前扫描，获得第一个顺序对a[i]
        while(i>=0&&a[i]>=a[i+1]){
            i--;
        }
        // 不存在下一个排列
        if(i<0)return -1;
        // 第二遍从后之前扫描，获得第一个元素a[j]，使得a[i]
        // 这样满足较小值尽可能地靠右，较大值尽可能地小
        int j=a.size()-1;
        while(j>=0&&a[i]>=a[j]){
            j--;
        }
        // 
        swap(a[i],a[j]);
        // 由于[i+1,n)之间的所有元素为降序，需要进行反转为升序序列
        reverse(a.begin()+i+1,a.end());
        long long x=stoll(a);
        return x>INT_MAX?-1:x;
    }
};