LeetCode: Next Permutation

思路分析

不能再经典的问题了，但是处理起来需要仔细思考细节。首先我们要寻找序列最右侧的最长非升连续序列，如果一直找到了开头，说明序列是完全的非升序，直接反转即可。如果我们找到一个最右连续非升序列，那么我们只需要把这个序列左边的第一个元素，与序列中最小的大于该元素的元素相交换，这样我们就保证了交换之后最右依然是一个连续非升序列。这样，我们将这个连续非升序列反转，就得到了字典序中原序列的下一个序列。

思路的核心在于，考虑我们是如何比较字典序大小的：由于单调非降的序列字典序最小，因此假设序列长度为m，如果一个序列刚好比另外一个序列大，那么一定有两者尽可能多的前n项相同，而大的序列在第n+1项取更大值，并且在它的[n + 2, m]中是单调非降的序列，从而保证后续部分最小。

代码

class Solution {
public:
    void nextPermutation(vector<int> &num) {
        if ( num.size() <= 1 ) return;
        int pos = -1;
        for ( int i = num.size() - 1; i >= 1; i-- ) {
            if ( num[i - 1] < num[i] ) {
                pos = i;
                break;
            }
        }
        if ( pos == -1 ) {
            reverse(num.begin(), num.end());
        } else {
            int _min = INT_MAX, target = -1;
            for ( int i = num.size() - 1; i >= pos; i-- ) {
                if ( num[i] > num[pos - 1] && num[i] < _min ) {
                    target = i;
                    _min = num[i];
                }
            }
            if ( target != -1 ) {
                swap(num[target], num[pos - 1]);
                reverse(num.begin() + pos, num.end());
            }
        }
    }
};