1053. 交换一次的先前排列.md

1053. 交换一次的先前排列

题目传送门

点击这里

解题思路

这道题的相似题意的也出现过，这种题型显然是用贪心算法来做的，如果想要交换一次得到字典序小于原数组的最大排列，首先交换的两个位置i和j要满足arr[i] > arr[j]，并且i要尽可能的大。所以先保证i的最大化，从大到小枚举i，在i之后遍历j，然后再保证j的最大化，且j的索引要尽可能小，从大到小枚举j，如果arr[i] > arr[j]，则交换i和j，并且返回结果。

代码

func prevPermOpt1(arr []int) []int {
	if len(arr) <= 1 {
		return arr
	}
	i := len(arr) - 2
	for i >= 0 && arr[i] <= arr[i+1] {
		i--
	}
	if i < 0 {
		return arr
	}
	t, j := 0, 0 // t用来记录最大的比arr[i]小的数，j用来记录最大的比arr[i]小的数的下标
	for k := i + 1; k < len(arr); k++ {
		if arr[k] < arr[i] && arr[k] > t {
			t = arr[k]
			j = k
		}
	}

	arr[i], arr[j] = arr[j], arr[i]
	return arr

}