Problem: 31. 下一个排列
文章目录
- 前言
- 思路
- 解法
- 总结
- Code
前言
题目是难以理解的，解法是匪夷所思的，我们是前途渺茫的。 --「鲁迅」
思路
开个玩笑。不过就像鲁迅说的一样，这道题的题目确实是难以理解的。
题目要求找出下一个字典序更大的排列，可以说是并没有什么思路。“更大”这样一个要求十分抽象，很难说找到一个角度去分解“更大”的要求。那么就只能看题解了吗，或者就试试。
- 第一个错误解法
观察一下简陋的用例们，至少我们知道一件事，把一个大的数字换到前面整个数字会变大，那么找到最大的方法是找到最大的数字，并将它换到前面一格？可是还有一些问题亟待解决，如果最大数字已经到最前面了呢，哦，找第二大的数字，等等，这不是优先队列吗。于是完整的思路就出来了，通过优先队列寻找最大的可向前置换的数字，并将它换到前面。
[1,3,2]，显然，他错了，这个数字被错误的置换成312，而正确的答案是213。 - 第二个错误解法
换大了，显然。我们从1开头的群组直接跳大了3开头的，属于是步子迈大了。那说明我们不必要找最大的可置换的数字，小一点也可以。那怎么找呢？会不会是从右往左找（这就靠点正确思路了）。从右往左找一个前面有比他小的数字，然后把这个数字放到比她小的数字前面。这样一来就变大了，而且不用一次就变大一个最大数字。很好，我又会了。哦，等等，换完之后再把后面的数字排序，这样就让后面的变成最小。
[4,2,0,2,3,2,0]，怎么会变成4220023呢，应该是4203022。不对劲，非常不对劲。 - 第三个正确解法
先把2换到最前面去了，这跨的太远了。我们的思路需要找跨步跨的小的。最小的不就是临近？那是不是这样呢，从右往左找第一个变小的数字 i，把 i 和 i+1 置换就好了。靠点谱了，然而还是需要考虑后面的数字，那索性排个序。哦吼，过了？
解法
当然，这个答案是可以的，但还是有点粗糙。经过对一些优秀题解（例如这个）的研究，最后解法优化到了下面的code。
总结
其实解题过程中遇到的错误远不止列出来的这几个，甚至从开始时我连字典序大小等价于数字大小都没有想到，因为“更大”这样一个概念的抽象。我们没办法描述一个没有见过的理论，或是只能很模糊的描述，这很正常。想出一个完善的理论可能很困难，那就从实践入手，从这个模糊的描述着手实现，找到不可覆盖的用例，从而抽取出理论中的正确部分，变现成新的理论，如此往复。
在实践过程中我们会失败很多次，写出很多错误解法，但每一个错误解法的背后，都是一次成功的尝试。失败总是贯穿人生始终的，但是从这个角度看，成功同样贯穿人生始终。
Code
class Solution {
public:
void nextPermutation(vector<int>& nums) {
for(int i = nums.size() - 2; i >= 0 ; i--) {
if(!is_rev(nums, i)) {
for(int j = nums.size() - 1; j > i; j--) {
if(nums[i] < nums[j]) {
swap(nums[i], nums[j]);
sort(nums.begin() + i + 1, nums.end());
return;
}
}
}
}
reverse(nums.begin(), nums.end());
}
bool is_rev(vector<int>& nums, int i) {
for(; i < nums.size() - 1; i++) {
if(nums[i] < nums[i + 1]) return false;
}
return true;
}
};
