leetcode 1053. 交换一次的先前排列-Toy模板网

这篇具有很好参考价值的文章主要介绍了leetcode 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

一开始把问题想复杂了，还专门用一个index记录最小点

class Solution(object):
    def prevPermOpt1(self, arr):
        """
        :type arr: List[int]
        :rtype: List[int]
        """
        length = len(arr)
        if length <=1: return arr
        min_index,min_value = length-1,arr[-1]
        for l in range(length-2,-1,-1):
            if arr[l] <= min_value:
                min_index,min_value = l,arr[l]
            else:
                j = min_index
                for i in range(l,length):
                    if arr[j] < arr[i] < arr[l]:
                        j = i
                arr[l],arr[j] = arr[j],arr[l]
                break
        return arr

后来想到还是从数组的尾巴往前找，如果 $a rr [l] <= a rr [l + 1]$ ，即满足单调递增，就继续往前找，直到不满足；不满足的时候，找后面一个小于 $a rr [l]$ 但是离 $a rr [l]$ 差距最小的点即可。文章来源地址https://www.toymoban.com/news/detail-613311.html

class Solution(object):
    def prevPermOpt1(self, arr):
        """
        :type arr: List[int]
        :rtype: List[int]
        """
        length = len(arr)
        if length <=1: return arr
        min_index,min_value = length-1,arr[-1]
        for l in range(length-2,-1,-1):
            if arr[l] <= arr[l+1]:
                continue
            else:
                j = l+1
                for i in range(l,length):
                    if arr[j] < arr[i] < arr[l]:
                        j = i
                arr[l],arr[j] = arr[j],arr[l]
                break
        return arr