Medium

题目描述

给定一个正整数数组 arr（不一定是不同的），返回通过恰好一次交换能够得到的字典序最大的、小于 arr 的排列。如果无法做到，则返回原数组。

注意交换是指交换两个数 arr[i] 和 arr[j] 的位置。

示例 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 <= 10^4
  • 1 <= arr[i] <= 10^4

解题思路

这道题要求找到比当前排列字典序小的最大排列，通过恰好一次交换实现。

核心思路是找到两个关键位置：

  1. 左位置：从右向左扫描，找到第一个满足 arr[i] > arr[i+1] 的位置 i。这是需要被替换的位置，因为它破坏了从右到左的非递增序列。
  2. 右位置：从右向左扫描，在 i 的右侧找到最大的、但小于 arr[i] 的数的位置 j。

为了确保结果是字典序最大的，我们需要：

  • 找到最左边的可交换位置（左位置）
  • 在该位置右侧找到尽可能大的、但仍小于左位置值的数（右位置）
  • 如果有多个相同的最大值，选择最右边的位置以避免不必要的交换

特殊情况：如果整个数组已经是非递增的（如 [3,2,1] 或 [1,1,5]），则无法通过交换得到更小的排列，返回原数组。

算法步骤：

  1. 从右向左找到第一个 arr[i] > arr[i+1] 的位置 i
  2. 如果没找到，说明数组已经是最小排列，直接返回
  3. 从右向左在 [i+1, n-1] 范围内找到最大的但小于 arr[i] 的数的位置 j
  4. 交换 arr[i] 和 arr[j]

代码实现

class Solution {
public:
    vector<int> prevPermOpt1(vector<int>& arr) {
        int n = arr.size();
        int left = -1;
        
        // 从右向左找到第一个 arr[i] > arr[i+1] 的位置
        for (int i = n - 2; i >= 0; i--) {
            if (arr[i] > arr[i + 1]) {
                left = i;
                break;
            }
        }
        
        // 如果没找到，说明数组已经是最小排列
        if (left == -1) {
            return arr;
        }
        
        // 在 left 右侧找到最大的但小于 arr[left] 的数
        int right = -1;
        for (int j = n - 1; j > left; j--) {
            if (arr[j] < arr[left]) {
                if (right == -1 || arr[j] > arr[right]) {
                    right = j;
                }
            }
        }
        
        // 交换
        swap(arr[left], arr[right]);
        return arr;
    }
};

class Solution:
    def prevPermOpt1(self, arr: List[int]) -> List[int]:
        n = len(arr)
        left = -1
        
        # 从右向左找到第一个 arr[i] > arr[i+1] 的位置
        for i in range(n - 2, -1, -1):
            if arr[i] > arr[i + 1]:
                left = i
                break
        
        # 如果没找到，说明数组已经是最小排列
        if left == -1:
            return arr
        
        # 在 left 右侧找到最大的但小于 arr[left] 的数
        right = -1
        for j in range(n - 1, left, -1):
            if arr[j] < arr[left]:
                if right == -1 or arr[j] > arr[right]:
                    right = j
        
        # 交换
        arr[left], arr[right] = arr[right], arr[left]
        return arr

public class Solution {
    public int[] PrevPermOpt1(int[] arr) {
        int n = arr.Length;
        int left = -1;
        
        // 从右向左找到第一个 arr[i] > arr[i+1] 的位置
        for (int i = n - 2; i >= 0; i--) {
            if (arr[i] > arr[i + 1]) {
                left = i;
                break;
            }
        }
        
        // 如果没找到，说明数组已经是最小排列
        if (left == -1) {
            return arr;
        }
        
        // 在 left 右侧找到最大的但小于 arr[left] 的数
        int right = -1;
        for (int j = n - 1; j > left; j--) {
            if (arr[j] < arr[left]) {
                if (right == -1 || arr[j] > arr[right]) {
                    right = j;
                }
            }
        }
        
        // 交换
        int temp = arr[left];
        arr[left] = arr[right];
        arr[right] = temp;
        
        return arr;
    }
}

/**
 * @param {number[]} arr
 * @return {number[]}
 */
var prevPermOpt1 = function(arr) {
    let n = arr.length;
    let i = n - 2;
    
    // Find the first decreasing element from right
    while (i >= 0 && arr[i] <= arr[i + 1]) {
        i--;
    }
    
    // If no such element exists, array is already smallest
    if (i < 0) {
        return arr;
    }
    
    // Find the largest element smaller than arr[i] to the right of i
    let j = n - 1;
    while (j > i && arr[j] >= arr[i]) {
        j--;
    }
    
    // Find the rightmost occurrence of arr[j] to avoid duplicates
    while (j > 0 && arr[j] === arr[j - 1]) {
        j--;
    }
    
    // Swap elements at i and j
    [arr[i], arr[j]] = [arr[j], arr[i]];
    
    return arr;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要遍历数组两次，每次最多 O(n)
空间复杂度O(1)只使用常数额外空间