public class Solution {
/*
* @param nums: A list of integers
* @return: A list of integers that's previous permuation
*/
public List<Integer> previousPermuation(List<Integer> nums) {
int cur = nums.size() - 1;
for(;cur >=1;cur--){
//找拐点，如果前面一个数大于当前数，前面一个数是拐点，
//在拐点后找一个最大的且比拐点小的数，和拐点交换
if(nums.get(cur - 1) > nums.get(cur)){
int start = cur;
int max = nums.get(start);
int index = start;
for(;start<nums.size();start++){
if(nums.get(start) > max && nums.get(start) < nums.get(cur - 1)){
max = nums.get(start);
index = start;
}
}
int temp = nums.get(cur - 1);
nums.set(cur - 1, nums.get(index));
nums.set(index, temp);
//对拐点之后的数从大到小排列
sortArray(nums,cur);
break;
}
}
System.out.println(cur);
if(cur <= 0){
sortArray(nums,0);
}
return nums;
}
//对数组从start位置开始大到小排列
void sortArray(List<Integer> nums,int start){
List<Integer> temp = new ArrayList<>();
for(int i=start;i<nums.size();i++){
temp.add(nums.get(i));
}
Collections.sort(temp);
int index = 0;
for(int i=temp.size() - 1;i>=0;i--){
nums.set(start + index, temp.get(i));
index ++;
}
}
}
