LeetCode-下一个排列

感觉从之前的题目开始写起来的话，会需要一定的时间去思考当时为什么这么写，那么每次写都是重新思考，除非进度能够赶上最新的刷题进度，所以决定从最新的开始往前写....最近又一直在刷LeetCode中文官网的题目，毕竟英语题目理解能力捉鸡。

原题地址： https://leetcode-cn.com/problems/next-permutation/

题目描述：

实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。

如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。

必须原地修改，只允许使用额外常数空间。

以下是一些例子，输入位于左侧列，其相应输出位于右侧列。

1,2,3 → 1,3,2

3,2,1 → 1,2,3

1,1,5 → 1,5,1

解题思路：

这题一开始我想错了方向，以为从右往左找到第一个值变小的索引后，将后续的元素排序即可，后来证明并不是这样的。正确的思路应该是：

1. 从右往左遍历，找到第一个值变小的索引i
2. 如果i等于-1，说明当前的数字序列是递减的，也就是没有更大的序列了，那么将整个数组反转即可，也就是变成最小的序列
3. 如果i大于等于0，那么就需要从右往左找到比nums[i]大的第一个元素，然后将nums[i]和该元素交换位置，再将坐标i之后的所有元素反转，也就是将坐标i之后的序列由最大变为最小。

通过以上三步，最终完成找到数组下一个排列的功能。

第3步中，之所以需要找刚好比nums[i]大的第一个元素，就是为了获得比当前排列恰好更大一级的排列。

如果有兴趣的话，可以看看LeetCode上关于这题的别人的一些题解：

中文：

https://leetcode-cn.com/problems/next-permutation/solution/

英文：

https://leetcode.com/problems/next-permutation/solution/

个人题解：

 public void nextPermutation(int[] nums) {
       // 从右往左遍历，找到值变小的索引
        int i = nums.length - 2;
        while (i >= 0 && nums[i + 1] <= nums[i]) {
            i--;
        }
        // 如果i>=0，从右往左找，找到值比nums[i]大的最小的值，交换
        if (i >= 0) {
            int j = nums.length - 1;
            while (j >= 0 && nums[j] <= nums[i]) {
                j--;
            }
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
        // 将nums中i之后的所有元素都逆转一下
        i += 1;
        int j = nums.length - 1;
        while (i < j) {
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
            i++;
            j--;
        }
    }

结果：

这题横跨了我两周的时间，然后由于本地代码没有提交到git，所以在我重装系统之后，一切记忆重新开始，最后成功的在失败了5次之后，将这题给解了出来，最后结果还算不错。