LC-1053. 交换一次的先前排列（上一个排列、下一个排列(贪心) ）
（上一个排列）1053. 交换一次的先前排列
难度中等56
给你一个正整数数组 arr（可能存在重复的元素），请你返回可在 一次交换（交换两数字 arr[i] 和 arr[j] 的位置）后得到的、按字典序排列小于 arr 的最大排列。
如果无法这么操作，就请返回原数组。
示例 1：
输入：arr = [3,2,1]
输出：[3,1,2]
解释：交换 2 和 1
示例 2：
输入：arr = [1,1,5]
输出：[1,1,5]
解释：已经是最小排列
示例 3：
输入：arr = [1,9,4,6,7]
输出：[1,7,4,6,9]
解释：交换 9 和 7
提示：
1 <= arr.length <= 1041 <= arr[i] <= 104
贪心
https://leetcode.cn/problems/previous-permutation-with-one-swap/solution/tan-xin-si-lu-jia-zheng-ming-on-by-xiao-6xjm7/
思路 从后向前找第一个arr[i] < arr[i - 1] 的位置 这个位置一定是 出现的第一个与后面的数交换后可能使字典序变小的数
（因为后面的数满足非递增关系（后向前）所以后面任意两个数交换都不会使得数组的字典序减小）
（为什么要选第一个能交换的呢？ 因为交换后当前位置一定会变小， 而前缀不变， 那么变小的位置一定是越靠后字典序越大）
由贪心思路得 一定是去换一个小于arr[i - 1] 的 最大的数 使得换后的字典序最大
（因为交换后i- 1的位置一定会发生变化 那么i- 1 后的数就可以忽略不看 当然前面的数由于没发生改变也可以不看 只比较当前位置 由字典序的定义 显然是当前位置越大， 字典序越大）
class Solution {
// 两次遍历
// 第一次从后往前找到第一个非递减的位置，即首个arr[i] > arr[i+1]的位置，若<0，则不需要任何对调
// 第二次从后往前找到首个比上一轮值arr[i]还要小并且最接近的数字
// 后面一步找到最接近的那个数字如果有很多个的话还要找最左边的那个
// 对调
public int[] prevPermOpt1(int[] arr) {
int n = arr.length;
int i = n-2, j = n-1;
while(i >= 0 && arr[i] <= arr[i+1]){
i--;
}
if(i < 0) return arr;
while(arr[i] <= arr[j] || j > 0 && arr[j-1] == arr[j]){
j--;
}
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
return arr;
}
}
31. 下一个排列
难度中等2137
整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。
- 例如，
arr = [1,2,3]，以下这些都可以视作arr的排列：[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1]。
整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列（即，其元素按升序排列）。
- 例如，
arr = [1,2,3]的下一个排列是[1,3,2]。 - 类似地，
arr = [2,3,1]的下一个排列是[3,1,2]。 - 而
arr = [3,2,1]的下一个排列是[1,2,3]，因为[3,2,1]不存在一个字典序更大的排列。
给你一个整数数组 nums ，找出 nums 的下一个排列。
必须** 原地 **修改，只允许使用额外常数空间。
示例 1：
输入：nums = [1,2,3]
输出：[1,3,2]
示例 2：
输入：nums = [3,2,1]
输出：[1,2,3]
示例 3：
输入：nums = [1,1,5]
输出：[1,5,1]
提示：
1 <= nums.length <= 1000 <= nums[i] <= 100
class Solution {
public void nextPermutation(int[] nums) {
int n = nums.length;
if(nums == null || n == 0) return;
// 从后往前查找第一次出现 nums[i] < nums[i+1] 的位置
int i = n-2;
while(i >= 0 && nums[i] >= nums[i+1]){
i--;
}
// if i == -1 nums 则整体逆序
if(i >= 0){
// 此时 nums[i+1, n-1] 降序, 查找其中 大于nums[i] 的最大下标，可以直接 从后往前 逆向找
// 因为有序 可以练习一下二分查找
int left = i+1, right = n-1;
while(left <= right){
int mid = (left + right) >> 1;
if(nums[mid] > nums[i]) left = mid+1;
else right = mid-1;
}
int j = right;
// 交换 i j
swap(nums, i, j);
}
// 此时 nums[i+1, n-1] 仍然降序，将其改为升序，只需要反转即可。
reverse(nums, i+1, n-1);
}
private void swap(int[] nums, int i, int j){
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
private void reverse(int[] nums, int i, int j){
while(i < j){
swap(nums, i++, j--);
}
}
}