[leetcode每日一题]4.3

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 <= arr.length <= 104
• 1 <= arr[i] <= 104

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] < arr[st[-1]]:
                st.append(i)
            if len(st) >= 2 and (a < st[-2] or a == st[-2] and arr[b] < arr[st[-1]]):
                a, b = st[-2], st[-1]
        if a != -1 and b != -1:
            arr[a], arr[b] = arr[b], arr[a]
        return arr

但是那样太慢了，根据上面的分析应该用贪心。每次去贪最后那个数。当然这个代码还是有点技巧的。这两次只判断相邻大小就很妙。

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）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。