31. Next Permutation

O(n) time 举例021找到第一个顺序对02，说明2开始已经是全逆序了，不可能再找到新的排列，所以只能找2后面的一个数和0交换，从后往前找到第一个比0大的是1，说明1以后的数都不比0大，不可能跟0交换，把1跟0交换以后，得到了一个新的排列，这时要将从2开始的全逆序翻转，即021 –> 120 –> 102

class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        n, x = len(nums), 0
        for i in range(n - 2, -1, -1):
            if nums[i] < nums[i + 1]:
                x = i
                break
        else:
            nums.reverse()
            return
        for i in range(n - 1, x, -1):
            if nums[i] > nums[x]:
                nums[x], nums[i] = nums[i], nums[x]
                break
        # nums[x + 1:] = reversed(nums[x + 1:])
        nums[x + 1:] = nums[n - 1:x:-1]
        # nums[x + 1:] = nums[x + 1:][::-1]

class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        for i in range(n - 2, -1, -1):
            if nums[i] < nums[i + 1]:
                break
        else:
            nums.reverse()
            return
        for j in range(n - 1, i, -1):
            if nums[j] > nums[i]:
                nums[i], nums[j] = nums[j], nums[i]
                break
        l, r = i + 1, n - 1
        while l < r:
            nums[l], nums[r] = nums[r], nums[l]
            l += 1
            r -= 1

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int n = nums.size();
        int i = n - 1;
        while (i > 0 && nums[i - 1] >= nums[i]) --i;
        if (i == 0) {
            reverse(begin(nums), end(nums));
            return;
        }
        int j = n - 1;
        while (nums[j] <= nums[i - 1]) --j;
        swap(nums[i - 1], nums[j]);
        reverse(begin(nums) + i, end(nums));
    }
};

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int n = nums.size();
        int i = n - 1;
        while (i > 0 && nums[i - 1] >= nums[i]) --i;
        if (i == 0) {
            reverse(begin(nums), end(nums));
            return;
        }
        int j = lower_bound(begin(nums) + i, end(nums), nums[i - 1], greater()) - begin(nums) - 1; // 二分查找右边降序序列里倒数第一个比nums[i - 1]大的数的位置
        swap(nums[i - 1], nums[j]);
        reverse(begin(nums) + i, end(nums));
    }
};

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int n = nums.size();
        if (n < 2) return;
        int l = 0, r = n - 1;
        int i1 = l, i2 = l;
        for (int i = r; i > l; --i) {
            if (nums[i - 1] < nums[i]) {
                i1 = i - 1;
                i2 = i;
                break;
            }
        }
        if (l == i2) {
            reverse(begin(nums), end(nums));
            return;
        }
        int i3 = i2;
        for (int i = r; i >= i2; --i) {
            if (nums[i] > nums[i1]) {
                i3 = i;
                break;
            }
        }
        swap(nums[i1], nums[i3]);
        reverse(begin(nums) + i2, end(nums));
    }
};

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int n = nums.size();
        nextPerm(nums, 0, n - 1); // 这里用的是左右闭区间
    }

    bool nextPerm(vector<int> &nums, int l, int r) {
        if (r <= l) return false; // 如果元素个数为0或者1，则没有下一个排列
        int idx1 = l, idx2 = l;
        for (int i = r - 1; i >= l; --i) { // 从后往前找到第一个相邻两元素后面的比前面大的
            if (nums[i] < nums[i + 1]) {
                idx1 = i;
                idx2 = i + 1;
                break;
            }
        }
        if (idx1 == idx2) { // 如果找不到，说明已经逆序，返回一个初始正序
            reverse(nums.begin() + l, nums.begin() + r + 1);
            return false;
        }
        int idx3 = l;
        for (int i = r; i >= l; --i) { // 从后往前找到第一个比之前找到的较小元素大的元素，与之交换
            if (nums[i] > nums[idx1]) {
                idx3 = i;
                break;
            }
        }
        swap(nums[idx1], nums[idx3]);
        reverse(nums.begin() + idx2, nums.begin() + r + 1); // 将从之前找到的较大元素到数组尾的所有元素翻转
        return true;
    }
};