1671. 得到山形数组的最少删除次数

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

考点

  • LIS
  • 前后缀分解

思路

一、问题描述与形式化建模

给定一个长度为 \(n\) 的整数数组 \[ \text{nums} = [a_0, a_1, \dots, a_{n-1}] \] 允许删除任意数量的元素（不改变剩余元素的相对顺序），目标是使剩余数组构成一个山形数组，并使删除的元素数量最少。

山形数组的定义

一个数组称为山形数组，当且仅当满足：

  1. 数组长度不少于 3；

  2. 存在某个下标 \(i\)（称为山顶），使得 \[ a_0 < a_1 < \cdots < a_i \quad\text{且}\quad a_i > a_{i+1} > \cdots > a_{m-1} \]

  3. 山顶左侧为严格递增，右侧为严格递减。

二、问题转化：最少删除 ⇔ 最长可保留山形结构

设最终保留下来的山形子序列长度为 \(L\)，则删除的元素数量为： \[ \text{删除数} = n - L \] 因此，原问题等价于：

在原数组中，寻找一条最长的山形子序列。

三、山形子序列的结构分解

若某个位置 \(i\) 作为山顶，则对应的山形子序列可以分为两部分：

  • 左侧部分：以 \(i\) 结尾的最长严格递增子序列；
  • 右侧部分：从 \(i\) 出发向右的最长严格递减子序列。

据此定义两个辅助数组： \[ \begin{aligned} \text{pre}[i] &= \text{以 } i \text{ 结尾的最长严格递增子序列长度} \\ \text{suf}[i] &= \text{从 } i \text{ 出发向右的最长严格递减结构的等价刻画} \end{aligned} \] 那么，以 \(i\) 为山顶的最大山形子序列长度为： \[ \text{mountain}(i) = \text{pre}[i] + \text{suf}[i] - 1 \] 减去 1 是因为山顶元素被左右两侧重复计算了一次。

四、核心实现思想

1. 左侧：正向计算严格递增结构

从左向右遍历数组，使用经典的「贪心 + 二分」方法计算： \[ \text{pre}[i] = \text{以 } i \text{ 结尾的最长严格递增子序列长度} \] 该方法维护一个数组，表示不同长度递增子序列的最小可能结尾值，时间复杂度为： \[ O(n \log n) \]

2. 右侧：反向遍历下的递增结构（等价于右侧递减）

为了刻画“从 \(i\) 向右的严格递减结构”，不显式构造最长递减子序列，而采用如下等价方式：

  • 从数组右端向左遍历；
  • 在该遍历顺序下，对当前元素应用与左侧相同的“最长严格递增子序列”算法；
  • 记所得结果为 suf[i]。

此时：

suf[i] 表示： 在从右向左遍历数组的过程中，以位置 \(i\) 结尾的最长严格递增子序列长度。

该数值在结构意义上，等价刻画了原数组中从位置 \(i\) 出发向右所能形成的最长严格递减子序列长度，因此可以直接用于山形右侧的建模。

五、最关键的剪枝条件：合法山顶判定

并非所有位置都可以作为山顶。根据山形数组的定义，合法山顶必须满足： \[ \text{pre}[i] \ge 2 \quad \text{且} \quad \text{suf}[i] \ge 2 \] 原因如下：

  • 左侧至少需要一个元素与山顶构成上升关系；
  • 右侧至少需要一个元素与山顶构成下降关系；
  • 否则无法形成长度不少于 3 的山形数组。

剪枝的意义

该条件用于：

  • 排除纯递增或纯递减的结构；
  • 防止非法山顶参与删除数计算；
  • 保证算法与题意严格一致。

这是本题中最重要、也最容易被忽略的剪枝条件。

六、删除数的计算方式

当位置 \(i\) 是合法山顶时：

  • 左侧需要删除的元素数量为： \[ (i + 1) - \text{pre}[i] \]

  • 右侧需要删除的元素数量为： \[ (n - i) - \text{suf}[i] \]

因此，以 \(i\) 为山顶的总删除数为： \[ \text{removals}(i) = (i + 1 - \text{pre}[i]) + (n - i - \text{suf}[i]) \] 遍历所有合法山顶，取最小值即为最终答案。

七、复杂度分析

  • 时间复杂度： 两次最长严格递增子序列计算，整体为 \[ O(n \log n) \]

  • 空间复杂度： 使用若干长度为 \(n\) 的辅助数组，为 \[ O(n) \]

八、AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
class Solution {
public:
    static const int maxn = 1e3 + 5;

    int minimumMountainRemovals(vector<int>& nums) {
        int n = nums.size();

        // pre[i]：以 i 结尾的最长严格递增子序列长度
        // suf[i]：从右向左遍历时，以 i 结尾的最长严格递增子序列长度
        //          等价刻画原数组中从 i 出发向右的最长严格递减结构
        vector<int> pre(n), suf(n), f;

        // 从左到右计算 pre[]
        for (int i = 0; i < n; ++i) {
            auto it = lower_bound(f.begin(), f.end(), nums[i]);
            pre[i] = it - f.begin() + 1;
            if (it == f.end())
                f.push_back(nums[i]);
            else
                *it = nums[i];
        }

        // 清空辅助数组，准备反向计算
        f.clear();

        // 从右到左计算 suf[]
        for (int i = n - 1; i >= 0; --i) {
            auto it = lower_bound(f.begin(), f.end(), nums[i]);
            suf[i] = it - f.begin() + 1;
            if (it == f.end())
                f.push_back(nums[i]);
            else
                *it = nums[i];
        }

        int res = INT_MAX >> 1;

        // 枚举山顶位置
        for (int i = 1; i < n - 1; ++i) {
            // 合法山顶必须左右两侧都至少存在一个元素
            if (pre[i] >= 2 && suf[i] >= 2)
                res = min(res, i + 1 - pre[i] + n - i - suf[i]);
        }

        return res;
    }
};