Medium

题目描述

给你一个整数数组 nums。数组中的每个元素都是 1、2 或 3。在每次操作中，你可以从 nums 中删除一个元素。返回使 nums 非递减所需的最少操作次数。

示例 1：

输入：nums = [2,1,3,2,1]
输出：3
解释：
一个最优解是删除 nums[0]、nums[2] 和 nums[3]。

示例 2：

输入：nums = [1,3,2,1,3,3]
输出：2
解释：
一个最优解是删除 nums[1] 和 nums[2]。

示例 3：

输入：nums = [2,2,2,2,3,3]
输出：0
解释：
nums 已经是非递减的。

约束条件：

  • 1 <= nums.length <= 100
  • 1 <= nums[i] <= 3

**进阶：**你能想出一个时间复杂度为 O(n) 的算法吗？

解题思路

这个问题要求我们删除最少的元素，使得数组变成非递减的。由于数组中只有 1、2、3 三个值，我们可以将问题转化为：保留最多的元素，使得剩余元素构成非递减序列。

方法一：枚举分割点（推荐）

核心思路是将数组分成三个连续区间：

  • 区间1：[0, i) - 全部保留值为1的元素
  • 区间2：[i, j) - 全部保留值为2的元素
  • 区间3：[j, n) - 全部保留值为3的元素

对于每种可能的分割方案 (i, j)，我们计算能保留的元素数量，然后用总长度减去最大保留数量即为最少删除次数。

具体做法：

  1. 枚举所有可能的分割点组合 (i, j)，其中 0 ≤ i ≤ j ≤ n
  2. 对每种分割方案，统计各区间内目标值的数量
  3. 计算该方案下能保留的元素总数
  4. 取所有方案中保留元素最多的情况

方法二：动态规划

也可以用DP求解最长非递减子序列，由于只有3个不同值，状态空间很小。

时间复杂度：O(n²) 枚举分割点，O(n) 动态规划
空间复杂度：O(1)

代码实现

class Solution {
public:
    int minimumOperations(vector<int>& nums) {
        int n = nums.size();
        int maxKeep = 0;
        
        // 枚举所有可能的分割点 (i, j)
        for (int i = 0; i <= n; i++) {
            for (int j = i; j <= n; j++) {
                int keep = 0;
                
                // 区间[0, i)保留所有1
                for (int k = 0; k < i; k++) {
                    if (nums[k] == 1) keep++;
                }
                
                // 区间[i, j)保留所有2
                for (int k = i; k < j; k++) {
                    if (nums[k] == 2) keep++;
                }
                
                // 区间[j, n)保留所有3
                for (int k = j; k < n; k++) {
                    if (nums[k] == 3) keep++;
                }
                
                maxKeep = max(maxKeep, keep);
            }
        }
        
        return n - maxKeep;
    }
};

class Solution:
    def minimumOperations(self, nums: List[int]) -> int:
        n = len(nums)
        max_keep = 0
        
        # 枚举所有可能的分割点 (i, j)
        for i in range(n + 1):
            for j in range(i, n + 1):
                keep = 0
                
                # 区间[0, i)保留所有1
                for k in range(i):
                    if nums[k] == 1:
                        keep += 1
                
                # 区间[i, j)保留所有2
                for k in range(i, j):
                    if nums[k] == 2:
                        keep += 1
                
                # 区间[j, n)保留所有3
                for k in range(j, n):
                    if nums[k] == 3:
                        keep += 1
                
                max_keep = max(max_keep, keep)
        
        return n - max_keep

public class Solution {
    public int MinimumOperations(IList<int> nums) {
        int n = nums.Count;
        int maxKeep = 0;
        
        // 枚举所有可能的分割点 (i, j)
        for (int i = 0; i <= n; i++) {
            for (int j = i; j <= n; j++) {
                int keep = 0;
                
                // 区间[0, i)保留所有1
                for (int k = 0; k < i; k++) {
                    if (nums[k] == 1) keep++;
                }
                
                // 区间[i, j)保留所有2
                for (int k = i; k < j; k++) {
                    if (nums[k] == 2) keep++;
                }
                
                // 区间[j, n)保留所有3
                for (int k = j; k < n; k++) {
                    if (nums[k] == 3) keep++;
                }
                
                maxKeep = Math.Max(maxKeep, keep);
            }
        }
        
        return n - maxKeep;
    }
}

/**
 * @param {number[]} nums
 * @return {number}
 */
var minimumOperations = function(nums) {
    const n = nums.length;
    const dp = Array(n).fill().map(() => Array(4).fill(0));
    
    // dp[i][j] = max length of non-decreasing subsequence ending at index i with value j
    for (let i = 0; i < n; i++) {
        for (let j = 1; j <= 3; j++) {
            if (nums[i] == j) {
                dp[i][j] = 1;
                if (i > 0) {
                    for (let k = 1; k <= j; k++) {
                        dp[i][j] = Math.max(dp[i][j], dp[i-1][k] + 1);
                    }
                }
            } else if (i > 0) {
                dp[i][j] = dp[i-1][j];
            }
        }
    }
    
    return n - Math.max(dp[n-1][1], dp[n-1][2], dp[n-1][3]);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

解法时间复杂度空间复杂度
枚举分割点O(n³)O(1)
动态规划O(n)O(1)

说明：

  • 枚举分割点方法：外层两个循环 O(n²)，内层统计 O(n)，总体 O(n³)
  • 由于数据规模较小(n ≤ 100)，O(n³) 的解法完全可行
  • 动态规划可以优化到 O(n)，但实现稍复杂，在此数据规模下枚举法更直观