• 思路分析：
  • 倒序遍歷：題目要求的是下一個排列，那么肯定數字的跳躍不能太大，所以可以比較好確定的是，遍歷的順序是倒序遍歷
  • 比較方向：對于每一個數字，需要找到右邊最大的比它小的數字，然后交換之后，剩余的數字進行升序排序

靈神題解

class Solution {
public:void nextPermutation(vector<int>& nums) {int n = nums.size();// 第一步：從右向左找到第一個小于右側相鄰數字的數 nums[i]int i = n - 2;while (i >= 0 && nums[i] >= nums[i + 1]) {i--;}// 如果找到了，進入第二步；否則跳過第二步，反轉整個數組if (i >= 0) {// 第二步：從右向左找到 nums[i] 右邊最小的大于 nums[i] 的數 nums[j]int j = n - 1;while (nums[j] <= nums[i]) {j--;}// 交換 nums[i] 和 nums[j]swap(nums[i], nums[j]);}// 第三步：反轉 [i+1, n-1]（如果上面跳過第二步，此時 i = -1）reverse(nums.begin() + i + 1, nums.end());}
};

錯誤代碼示例：

• 我開始寫的思路是，倒序遍歷的思路沒問題，但是找到合適的交換對象的時候，我找的是每一個數字左邊第一個比它小的數字，然后交換的位置的右邊再進行升序排列

• 錯誤分析：下一個排列，應該是盡量操作右邊的數字，并且我們是倒序遍歷的，所以遍歷過的部分的情況可以知道，所以尋找的交換順序的時候，還是往右邊進行考慮