2826. 将三个组排序

发表于 分类于 阅读次数： Waline： 本文字数： 1.4k 阅读时长 ≈ 5 分钟

考点

  • LIS
  • 状态机DP
  • 最长单调不减序列

思路

问题概述

给定一个仅包含数字 1、2 和 3 的数组 nums，我们的任务是通过最少的删除操作，使得数组 nums 成为一个单调不减的数组。我们可以通过以下两种方法来解决该问题：一种是使用最长单调不减子序列（LIS）的方法，另一种是通过动态规划（DP）的方法。接下来，我们将详细探讨这两种方法。

方法一：转化为最长单调不减子序列

思路

这个问题可以转化为一个最长单调不减子序列的问题。核心的思想是：在数组中找到一个最长的子序列，使得该子序列是单调不减的。我们可以将数组 nums 中的非单调部分删除，从而使得整个数组变得单调不减。删除的次数就是原数组的长度减去最长单调不减子序列的长度。

具体步骤

  1. 初始化一个空的数组 f，该数组用于维护当前已经找到的单调不减子序列。
  2. 遍历数组 nums 中的每一个元素，对于每个元素 x，我们找到 f 中第一个大于 x 的位置，并将其替换成 x。如果 x 大于 f 中所有元素，就将其添加到 f 的末尾。
  3. 最终，f 中的元素个数即为最长单调不减子序列的长度。最少的删除次数就是原数组的长度减去 f 的长度。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    static const int maxn = 105;
    int minimumOperations(vector<int>& nums) {
        vector<int> f;
        for (int& x : nums) {
            // 使用 upper_bound 找到第一个大于 x 的位置
            auto it = upper_bound(f.begin(), f.end(), x);
            if (it == f.end())
                f.push_back(x);  // 如果没找到，添加到数组末尾
            else
                *it = x;  // 否则替换掉该位置的元素
        }
        // 最少删除次数 = 总长度 - 最长单调不减子序列的长度
        return nums.size() - f.size();
    }
};

解释

  • upper_bound(f.begin(), f.end(), x)：此函数返回 f 中第一个大于 x 的位置。若所有元素都小于或等于 x，则返回 f.end()。
  • f.push_back(x)：如果没有找到大于 x 的位置，将 x 添加到 f 中。
  • *it = x：如果找到一个大于 x 的元素，就用 x 替换它，以保证 f 中的子序列始终是单调不减的。
  • 最终，f.size() 就是最长单调不减子序列的长度，最少删除次数就是 nums.size() - f.size()。

方法二：动态规划（状态机）

思路

通过动态规划（DP），我们可以维护三个状态：当前序列的结尾是 1、2 还是 3。每次根据当前元素的值来更新相应的状态，最终返回最少删除次数。

状态定义

  • f[i][1]：前 i 个元素形成的单调不减序列，且最后一个元素是 1 时的最小删除次数。
  • f[i][2]：前 i 个元素形成的单调不减序列，且最后一个元素是 2 时的最小删除次数。
  • f[i][3]：前 i 个元素形成的单调不减序列，且最后一个元素是 3 时的最小删除次数。

状态转移方程

  1. 初始化：f[0][1] = f[0][2] = f[0][3] = 0，即初始时没有元素时的删除次数为 0。
  2. 转移：
    • 如果 nums[i-1] == 1，则 f[i][1] = f[i-1][1]。
    • 如果 nums[i-1] == 2，则 f[i][2] = min(f[i-1][1], f[i-1][2])。
    • 如果 nums[i-1] == 3，则 f[i][3] = min(f[i-1][1], f[i-1][2], f[i-1][3])。
  3. 结果：最少删除次数即为 min(f[n][1], f[n][2], f[n][3])，其中 n 是数组的长度。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    static const int maxn = 105;
    int minimumOperations(vector<int>& nums) {
        int f[maxn][4], n = nums.size();
        f[0][1] = f[0][2] = f[0][3] = 0;
        for (int i = 1; i <= n; ++i) {
            if (nums[i - 1] == 1)
                f[i][1] = f[i - 1][1];
            else
                f[i][1] = f[i - 1][1] + 1;
            if (nums[i - 1] == 2)
                f[i][2] = min(f[i - 1][1], f[i - 1][2]);
            else
                f[i][2] = f[i - 1][2] + 1;
            if (nums[i - 1] == 3)
                f[i][3] = min(f[i - 1][1], min(f[i - 1][2], f[i - 1][3]));
            else
                f[i][3] = f[i - 1][3] + 1;
        }
        return min(f[n][1], min(f[n][2], f[n][3]));
    }
};

解释

  • 初始值：f[0][1] = f[0][2] = f[0][3] = 0。
  • 转移关系：根据当前数字 nums[i-1] 的值更新状态。如果当前值与目标结尾相同，则不需要删除，直接继承前一个状态；否则需要加 1。
  • 最终答案：返回 min(f[n][1], f[n][2], f[n][3])，即最后一个元素为 1、2 或 3 时的最小删除次数。

方法三：滚动数组优化

通过滚动数组的优化，我们可以将原本二维的 DP 数组降为一维数组，从而节省空间。

思路

我们可以使用三个变量 a、b 和 c 来代替原来的二维数组 f[i][1]、f[i][2] 和 f[i][3]，以记录当前状态。在每次循环时，更新这三个变量的值。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    static const int maxn = 105;
    int minimumOperations(vector<int>& nums) {
        int n = nums.size(), a = 0, b = 0, c = 0;
        for (int i = 1; i <= n; ++i) {
            int ta = nums[i - 1] == 1 ? a : a + 1;
            int tb = nums[i - 1] == 2 ? min(a, b) : b + 1;
            int tc = nums[i - 1] == 3 ? min({a, b, c}) : c + 1;
            a = ta, b = tb, c = tc;
        }
        return min({a, b, c});
    }
};

解释

  • a, b, c 分别对应 f[i-1][1], f[i-1][2], f[i-1][3]。
  • 每次根据当前元素的值，计算出新的状态 ta、tb 和 tc，并更新 a、b 和 c。
  • 最终返回 min(a, b, c)，即最小的删除次数。