What pattern does Sorting Three Groups follow?

Sorting Three Groups uses state transition dynamic programming, tracking minimum removals for sequences ending in each group.

Can this approach handle arrays longer than 100 elements?

Yes, the DP approach scales linearly with array length, but constraints limit length to 100 in this problem.

Why not use a greedy method to remove elements?

Greedy removal can fail because it does not account for future elements; dynamic programming ensures minimal total removals.

How do equal elements affect DP transitions?

Equal elements can be included without removal if they maintain non-decreasing order, preserving optimal DP states.

Is rolling array optimization necessary?

Rolling arrays reduce space from O(n*3) to O(3), which is efficient for this problem but optional for correctness.

#2826

Medium

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

将三个组排序

给你一个整数数组 nums 。 nums 的每个元素是 1，2 或 3。在每次操作中，你可以删除 nums 中的一个元素。返回使 nums 成为非递减顺序所需操作数的最小值。示例 1：输入： nums = [2,1,3,2,1] 输出： 3 解释：其中一个最优方案是删除 nums[0]…

数组二分查找动态规划

题目描述

给你一个整数数组 nums 。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) 时间复杂度以内的算法解决吗？

lightbulb

解题思路

方法一：动态规划

我们定义 $f[i][j]$ 表示将前 $i$ 个数变成美丽数组，并且第 $i$ 个数变成 $j+1$ 的最少操作次数。那么答案就是 $\min(f[n][0], f[n][1], f[n][2])$ 。

我们可以枚举第 $i$ 个数变成 $j+1$ 的所有情况，然后取最小值。这里我们可以用滚动数组优化空间复杂度。

时间复杂度 $O(n)$ ，其中 $n$ 是数组的长度。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

class Solution:
    def minimumOperations(self, nums: List[int]) -> int:
        f = [0] * 3
        for x in nums:
            g = [0] * 3
            if x == 1:
                g[0] = f[0]
                g[1] = min(f[:2]) + 1
                g[2] = min(f) + 1
            elif x == 2:
                g[0] = f[0] + 1
                g[1] = min(f[:2])
                g[2] = min(f) + 1
            else:
                g[0] = f[0] + 1
                g[1] = min(f[:2]) + 1
                g[2] = min(f)
            f = g
        return min(f)

speed

复杂度分析

指标	值
时间	and space complexity depend on tracking three states per array element. Iterating through n elements with constant state updates gives O(n) time and O(1) extra space using rolling states. Full DP table requires O(n*3) space.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Pay attention to the order of 1s, 2s, and 3s for the DP transitions.
question_mark
Clarify handling of elements equal to the last group to avoid unnecessary removals.
question_mark
Consider whether rolling state arrays can optimize space complexity.

warning

常见陷阱

外企场景

error
Failing to update all three DP states at each step can miss the optimal removal path.
error
Confusing element equality with a required removal rather than a valid transition.
error
Attempting greedy removal without considering dynamic programming may overcount operations.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Arrays with more than three distinct numbers following a similar state transition DP.
arrow_right_alt
Allowing swap operations instead of removals, adjusting the DP transitions accordingly.
arrow_right_alt
Finding the longest non-decreasing subsequence directly and computing removals as n minus its length.

help

常见问题

外企场景

继续练习

#2830 销售利润最大化 #2926 平衡子序列的最大和 #2713 矩阵中严格递增的单元格数