Next Permutation

这是一道很经典的孤立问题，个人没有发现任何题有和此题类似的算法或者逻辑，而且虽然此题看上去像是backtracking类的permutation题简化版，但实际上从逻辑处理上没有太多可以参考的地方，这道题的逻辑是先把数组从右向左扫描找到第一个有下降趋势的点，然后从这个点往右扫找最小的比它大数，然后将这两个数互换，最后把这两个数之间的区间反转过来即使下一个permutation，至今都没有太明白这是个什么道理_(:зゝ∠)_

public class Solution {
    public void nextPermutation(int[] nums) {
        int i = nums.length - 2;
        while (i >= 0 && nums[i + 1] <= nums[i]) {
            i--;
        }
        if (i >= 0) {
            int j = nums.length - 1;
            while (j >= 0 && nums[j] <= nums[i]) {
                j--;
            }
            swap(nums, i, j);
        }
        reverse(nums, i + 1);
    }

    private void reverse(int[] nums, int start) {
        int i = start, j = nums.length - 1;
        while (i < j) {
            swap(nums, i, j);
            i++;
            j--;
        }
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

下面是二刷自己的代码，再过一遍思路的话就是首先从右到左找第一个值下降的点的位置leftbound，如果没有这个点直接反转整个数组，如果有则从这个点再往回扫找到比这个点大的值最小的那个点，这里肯定是有这个点的，找到这个点之后两点交换然后对leftbound之后的（不包括leftbound）数组进行反转就是结果了，下面是代码

class Solution(object):
    def nextPermutation(self, nums):
        """
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        left_bound = -1
        for i in xrange(n - 2, -1, -1):
            if nums[i] < nums[i + 1]:
                left_bound = i
                break

        if left_bound == -1:
            self.reverse(nums, 0, n - 1)
            return

        cmp = sys.maxint
        right_bound = n
        for i in xrange(left_bound, n):
            if nums[i] > nums[left_bound]:
                if nums[i] - nums[left_bound] <= cmp:
                    cmp = nums[i] - nums[left_bound]
                    right_bound = i

        nums[left_bound], nums[right_bound] = nums[right_bound], nums[left_bound]
        self.reverse(nums, left_bound + 1, n - 1)

    def reverse(self, nums, start, end):
        while start < end:
            nums[start], nums[end] = nums[end], nums[start]
            start += 1
            end -= 1