题目大意
给出一个数组nums，求出nums的下一个permutation。 比如
{1,2,3,4}
，他的下一个permutation是
{1,2,4,3}
而且permutation会循环，如
{4,3,2,1}
，他的下一个permutation是
{1,2,3,4}
解题思路
给出一个数组，第一个permutation肯定是递增的，最后一个permutation是递减的。找下一个permutation的时候，要做改变的位置都是尽量靠右的，所以是从后往前遍历，一旦发现不满足递减的子序列，就可以做处理了。
处理过程： 停下来的时候是因为我们找到了一个数
nums[i]<nums[i+1]
，要找到nums[i]这个数的下一个数，这个数就在范围nums[i+1, end]里面找，找出nums[i+1, end]中最小且大于nums[i]的数来替代nums[i]，注意，nums[i+1, end]里面里面有可能有比nums[i]小的数，这样的数不应该考虑，因为按照permutation的规则，这样的数已经放过在i的位置了。那么，假设找到的这个数的位置是j，就可以swap(i, j)，然后在对后面nums[i+1, end]排个序。
有一个分析写的挺好的，引用一下：
代码
class Solution {
public:
void nextPermutation(
vector<int>& nums) {
int stopInd = -
1, temp =
0, nextInd =
int(nums.size()) -
1;
for (
int i =
int(nums.size()) -
1; i >
0; i--) {
if (nums[i -
1] < nums[i]) {
stopInd = i -
1;
break;
}
}
if (stopInd >=
0) {
for (
int i =
int(nums.size()) -
1; i > stopInd; i--) {
if (nums[i] <= nums[stopInd]) {
nextInd--;
continue;
}
}
temp = nums[stopInd];
nums[stopInd] = nums[nextInd];
nums[nextInd] = temp;
}
sort(nums.begin() + stopInd +
1, nums.end());
}
};
int main(
int argc,
const char * argv[]) {
Solution s;
vector<int> n = {
3,
2,
1};
s.nextPermutation(n);
return 0;
}
