1053. 交换一次的先前排列
提示
中等
80
相关企业
给你一个正整数数组 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 41 4
Solution
经过一早上的思考得出，如果想要达到字典序最小的元素，则必须选取最大的下标i满足i后面的位置存在数比arr[i]小，并与比其小的最大的那个数进行交换。如果有多个最大的那个数，那么交换最前面的那个最大的数。
我的做法是单调栈，每次考虑一个新元素的时候就更新可以交换的数。
class Solution:
def prevPermOpt1(self, arr: List[int]) -> List[int]:
st = []
a, b = -1, -1
for i in range(len(arr)):
while st and arr[i] >= arr[st[-1]]:
st.pop()
if not st or arr[i] = 2 and (a 但是那样太慢了，根据上面的分析应该用贪心。每次去贪最后那个数。当然这个代码还是有点技巧的。这两次只判断相邻大小就很妙。
class Solution:
def prevPermOpt1(self, arr: List[int]) -> List[int]:
n = len(arr)
for i in range(n - 2, -1, -1):
if arr[i] > arr[i + 1]: # 只要判断相邻的大小
j = n - 1
while arr[j] >= arr[i] or arr[j] == arr[j - 1]: # 只要判断相邻的大小
j -= 1
arr[i], arr[j] = arr[j], arr[i]
break
return arr
作者：力扣官方题解
链接：https://leetcode.cn/problems/previous-permutation-with-one-swap/solutions/2202472/jiao-huan-yi-ci-de-xian-qian-pai-lie-by-evkqi/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
机房租用，北京机房租用，IDC机房托管， http://www.e1idc.net
