$31

robot · robot · commit 70d7f4c0f2c6 · 2022-07-04T00:27:14.000+08:00
diff --git a/problems/31.next-permutation.md b/problems/31.next-permutation.md
@@ -33,31 +33,35 @@ https://leetcode-cn.com/problems/next-permutation/
 
 符合直觉的方法是按顺序求出所有的排列，如果当前排列等于 nums，那么我直接取下一个但是这种做法不符合 constant space 要求（题目要求直接修改原数组）,时间复杂度也太高，为 O(n!),肯定不是合适的解。
 
-这种题目比较抽象，写几个例子通常会帮助理解问题的规律。我找了几个例子，其中蓝色背景表示的是当前数字找下一个更大排列的时候`需要改变的元素`.
+我们也可以以回溯的角度来思考这个问题，即从后往前思考。
 
-![31.next-permutation](https://tva1.sinaimg.cn/large/007S8ZIlly1ghlu4t2qbfj30cx0703yw.jpg)
-
-我们不难发现，蓝色的数字都是从后往前第一个不递增的元素，并且我们的下一个更大的排列
-只需要改变蓝色的以及之后部分即可，前面的不需要变。
-
-那么怎么改变蓝色的以及后面部分呢？为了使增量最小，
-由于前面我们观察发现，其实剩下的元素从左到右是递减的，而我们想要变成递增的，我们只需要不断交换首尾元素即可。
-
-另外我们也可以以回溯的角度来思考这个问题，让我们先回溯一次：
+让我们先回溯一次，即思考最后一个数字是如何被添加的。
 
 ![31.next-permutation-2](https://tva1.sinaimg.cn/large/007S8ZIlly1ghlu4tmf9vj30d204r74f.jpg)
 
-这个时候可以选择的元素只有 2，我们无法组成更大的排列，我们继续回溯，直到如图：
+由于这个时候可以选择的元素只有 2，我们无法组成更大的排列，我们继续回溯，直到如图：
 
 ![31.next-permutation-3](https://tva1.sinaimg.cn/large/007S8ZIlly1ghlu4ukjgej30go07imxq.jpg)
 
-我们发现我们可以交换 4 或者 2 实现变大的效果，但是要保证变大的幅度最小（下一个更大），
-我们需要选择最小的，由于之前我们发现后面是从左到右递减的，显然就是交换最右面大于 1 的。
+我们发现我们可以交换 4 和 2 就会变小，因此我们不能进行交换。
+
+接下来碰到了 1。 我们有两个选择：
+
+- 1 和 2 进行交换
+- 1 和 4 进行交换
 
-之后就是不断交换使之幅度最小：
+两种交换都能使得结果更大，但是 和 2 交换能够使得增值最小，也就是题目中的下一个更大的效果。因此我们 1 和 2 进行交换。
 
 ![31.next-permutation-4](https://tva1.sinaimg.cn/large/007S8ZIlly1ghlu4vhrisj30h00cmwfn.jpg)
 
+还需要继续往高位看么？不需要，因为交换高位得到的增幅一定比交换低位大，这是一个贪心的思想。
+
+那么如何保证增幅最小呢? 其实只需要将 1 后面的数字按照从小到大进行排列即可。
+
+注意到 1 后面的数已经是从大到小排列了（非严格递减），我们其实只需要用双指针交换即可，而不需要真正地排序。
+
+> 1 后面的数一定是从大到小排好序了吗？当然，否则，我们找到第一个可以交换的回溯点就不是 1 了，和 1 是第一个可以交换的回溯点矛盾。因为第一个可以交换的回溯点其实就是从后往前第一个递减的值。
+
 ## 关键点解析
 
 - 写几个例子通常会帮助理解问题的规律
@@ -120,33 +124,21 @@ Python3 Code:
 
 ```python
 class Solution:
-    def nextPermutation(self, nums):
-        """
-        Do not return anything, modify nums in-place instead.
-        :param list nums
-        """
-        # 第一步，从后往前，找到下降点
-        down_index = None
-        for i in range(len(nums)-2, -1, -1):
-            if nums[i] < nums[i+1]:
-                down_index = i
-                break
-        # 如果没有下降点，重新排列
-        if down_index is None:
-            nums.reverse()
-        # 如果有下降点
-        else:
-            # 第二步，从后往前，找到比下降点大的数，对换位置
-            for i in range(len(nums)-1, i, -1):
-                if nums[down_index] < nums[i]:
-                    nums[down_index], nums[i] = nums[i], nums[down_index]
-                    break
-            # 第三部，重新排列下降点之后的数
-            i, j = down_index+1, len(nums)-1
-            while i < j:
-                nums[i], nums[j] = nums[j], nums[i]
-                i += 1
+    def nextPermutation(self, nums: List[int]) -> None:
+        i = len(nums) - 2
+        while i >= 0 and nums[i] >= nums[i + 1]:
+            i -= 1
+        if i >= 0:
+            j = len(nums) - 1
+            while j >= 0 and nums[i] >= nums[j]:
                 j -= 1
+            nums[i], nums[j] = nums[j], nums[i]
+
+        left, right = i + 1, len(nums) - 1
+        while left < right:
+            nums[left], nums[right] = nums[right], nums[left]
+            left += 1
+            right -= 1
 ```
 
 CPP Code:
