Given an array of positive integers arr (not necessarily distinct), return the lexicographically largest permutation that is smaller than arr, that can be made with exactly one swap. If it cannot be done, then return the same array.
Note that a swap exchanges the positions of two numbers arr[i] and arr[j]
Example 1:
Input: arr = [3,2,1]
Output: [3,1,2]
Explanation: Swapping 2 and 1.
Example 2:
Input: arr = [1,1,5]
Output: [1,1,5]
Explanation: This is already the smallest permutation.
Example 3:
Input: arr = [1,9,4,6,7]
Output: [1,7,4,6,9]
Explanation: Swapping 9 and 7.
Constraints:
1 <= arr.length <= 104
1 <= arr[i] <= 104
动态规划
基本: 要变小必须是低位元素x和高位元素y交换，满足y>x
1. 对于问题arr = [a,b,c,d], 最小改动为在尾部添加x
2. 假设对于子问题arr需要交换的两个元素索引为left，right。x对子问题的影响为
2.1 x不使用则，left right等于子问题的left right。
2.2 x使用则只能在区间[left,x)使用
2.2.1当x和索引大于left的元素y交换时必定可以得出更大且小于初始arr的结果所以left更新为index(y),right更新为x。
2.2.2当x和索引等于left的元素交换时，这需要比较arr[right]和x谁更大，如果x大于arr[right]则更新right=index(x).
因为是要找出小于原始arr的第一大值，所以在可选集中选择最大的。
func prevPermOpt1(arr []int) []int {
if len(arr) <= 1 {
return arr
}
left, right := 0, 0
for i := 1; i < len(arr); i++ {
for j := i - 1; j >= left; j-- {
if arr[j] <= arr[i] {
continue
}
if j > left {
left, right = j, i
break
}
if j == left {
if left == right || arr[right] < arr[i] {
right = i
}
break
}
}
//fmt.Printf("%+v, %+v\n", arr[left], arr[right])
}
// swap
arr[left], arr[right] = arr[right], arr[left]
return arr
}