【Java|golang】1053. 交换一次的先前排列

给你一个正整数数组 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 <= 104 1 <= arr[i] <= 104

处理方式为： 第一步：从当前序列的后往前找，找到第一个降序的位置（A[i]>A[i+1]），则必存在能构造比当前小的序列。 第二步：把A[i]后面的数字中，小于A[i]且最接近A[i]的值的数字找出来，和A[i]交换。 为什么第一步不再往前找，因为往前找更换，会让小的值出现在高位，导致不是最大字典序。

public int[] prevPermOpt1(int[] arr) {
          
   
        for (int i = arr.length - 1; i > 0; i--) {
          
   
            if (arr[i-1]>arr[i]){
          
   
                int max=arr[i];
                int index=i;
                for (int j = index; j < arr.length; j++) {
          
   
                    if (arr[i-1]>arr[j]&&arr[j]>max){
          
   
                        max=arr[j];
                        index=j;
                    }
                }
                int dp=arr[i-1];
                arr[i-1]=arr[index];
                arr[index]=dp;
                break;
            }
        }
        return arr;
    }

func prevPermOpt1(arr []int) []int {
          
   
	for i := len(arr) - 1; i > 0; i-- {
          
   
		if arr[i-1]>arr[i]{
          
   
			max,index:=arr[i],i
			for j := index; j < len(arr); j++ {
          
   
				if arr[i-1]>arr[j]&&arr[j]>max{
          
   
					max=arr[j]
					index=j
				}
			}
			arr[i-1],arr[index]=arr[index],arr[i-1]
			break
		}
	}
	return arr
}