leetcode 31Next Permutation

class Solution { public: void nextPermutation(vector<int>& nums) { int first=-1; for(int i = nums.size()-2 ; i>=0 ; i--) { if(nums[i]<nums[i+1]) { first = i; break; } } if(first == -1) {reverse(nums.begin(),nums.end());return;} int second; for(int i = nums.size()-1; i>=0; i--) { if(nums[i]>nums[first]) { second = i; break; } } swap(nums[first],nums[second]); reverse(nums.begin()+first+1,nums.end()); } }; 这道题一开始看了半天没看懂，后来才发现是求组成当前序列的全排列的下一个，如 1 2 3组成的全排列一共有6个按顺序来说是123,132,213,231,312,321,即每次都要增加最少。特别题目中提到321的下一个全排列是123，也就是最小的，所以如果对于类似于643541的下一个全排列，让它增加最少，后三位 5 4 1都是按照降序，排列的，已经达到了局部最小，所以就一定要在3上做文章了。将3替换成后三位比它大的最小数 就是4。换一下位置变为644531。显然后三位 135才是最小的。那么它的下一个全排列就是644135了。

代码也可以根据上述思想来解答，先找出从后向前，非升序的第一个数，然后再从后向前找到第一个比它大的数换一下位置，因为后面的数还是按照升序排列，反转一下就成了最小了。