Leetcode|从后向前找首对升序对再交换右侧数并升序|31. 下一个排列

本文主要是介绍Leetcode|从后向前找首对升序对再交换右侧数并升序|31. 下一个排列，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

在这里插入图片描述

两遍扫描

以求 12385764 的下一个排列为例：

在这里插入图片描述
从后向前找到第一对严格升序对，如5, 7

其中nums[left] = 5，即left = 4
然后找到left右侧最小的比5大的数的索引，即nums[right] = 6, right = 6

交换5和6

然后保证left后的数组保持升序

原地修改后的数组即为下一个排列
在这里插入图片描述

class Solution {
public:void nextPermutation(vector<int>& nums) {// 待交换元素的左索引和右索引，以及next表示比nums[left]大的最小的数int left = 0, right = 0, next = INT_MAX;int size = nums.size();// 1.找到连续升序的左索引leftfor (int i = size - 1; i > 0; i--)if (nums[i - 1] < nums[i]) {left = i - 1;break;}// 2.找到left后大于nums[left]众多元素中最小的元素next对应的索引rightfor (int i = left + 1; i < size; i++)if (nums[i] > nums[left]) {next = min(next, nums[i]);right = i;  // 无break}// 3.若不存在可交换的右元素，则说明当前数组是最大(降序)排列数组，直接返回升序数组即可if (right == 0)sort(nums.begin(), nums.end());else {  // 否则交换左右元素，然后升序left后的元素swap(nums[left], nums[right]);sort(nums.begin() + left + 1, nums.end());}   }
};