實現(xiàn)獲取下一個排列的函數(shù)腹备，算法需要將給定數(shù)字序列重新排列成字典序中下一個更大的排列。
如果不存在下一個更大的排列师幕，則將數(shù)字重新排列成最小的排列（即升序排列）专控。
必須原地修改抹凳，只允許使用額外常數(shù)空間。
以下是一些例子伦腐，輸入位于左側列赢底，其相應輸出位于右側列。
1,2,3→1,3,2
3,2,1→1,2,3
1,1,5→1,5,1
首先柏蘑，我們觀察到對于任何給定序列的降序幸冻，沒有可能的下一個更大的排列。
例如咳焚，以下數(shù)組不可能有下一個排列：
[9, 5, 4, 3, 1]
我們需要從右邊找到第一對兩個連續(xù)的數(shù)字 a[i] 和 a[i?1]洽损，它們滿足
a[i]>a[i?1]。現(xiàn)在革半，沒有對 a[i?1] 右側的重新排列可以創(chuàng)建更大的排列碑定，因為該子數(shù)組由數(shù)字按降序組成。因此督惰，我們需要重新排列 a[i?1] 右邊的數(shù)字不傅，包括它自己。
現(xiàn)在赏胚，什么樣的重新排列將產(chǎn)生下一個更大的數(shù)字？我們想要創(chuàng)建比當前更大的排列商虐。因此觉阅，我們需要將數(shù)字 a[i?1] 替換為位于其右側區(qū)域的數(shù)字中比它更大的數(shù)字崖疤，例如 a[j]。
我們交換數(shù)字 a[i?1] 和 a[j]典勇。我們現(xiàn)在在索引 i?1 處有正確的數(shù)字劫哼。 但目前的排列仍然不是我們正在尋找的排列。我們需要通過僅使用 a[i?1]右邊的數(shù)字來形成最小的排列割笙。 因此权烧，我們需要放置那些按升序排列的數(shù)字，以獲得最小的排列伤溉。
但是般码，請記住，在從右側掃描數(shù)字時乱顾，我們只是繼續(xù)遞減索引直到我們找到
a[i] 和 a[i?1] 這對數(shù)板祝。其中，a[i]>a[i?1]走净。因此券时，a[i?1] 右邊的所有數(shù)字都已按降序排序。此外伏伯，交換 a[i?1] 和 a[j] 并未改變該順序橘洞。因此，我們只需要反轉
a[i?1] 之后的數(shù)字说搅，以獲得下一個最小的字典排列炸枣。
class Solution {
public void nextPermutation(int[] nums) {
int i = nums.length - 2;
while (i >= 0 && nums[i + 1] <= nums[i]) {
i--;
}
if (i >= 0) {
int j = nums.length - 1;
while (j >= 0 && nums[j] <= nums[i]) {
j--;
}
swap(nums, i, j);
}
reverse(nums, i + 1);
}
private void reverse(int[] nums, int start) {
int i = start, j = nums.length - 1;
while (i < j) {
swap(nums, i, j);
i++;
j--;
}
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
