【每日一题】得到山形数组的最少删除次数

Tag

【最长递增子序列】【数组】【2023-12-22】

---

题目来源

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

---

解题思路

方法一：最长递增子序列

前后缀分解

根据前后缀思想，以 nums[i] 为山顶的山形数组可以看成 nums[i] 左侧以其作为结尾的最长递增子序列，我们记左侧的最长递增子序列的长度为 pre[i]，拼接上 nums[i] 右侧以其作为结尾的最长递减子序列，我们记右侧的最长递减子序列的长度为 suf[i]，此时以 nums[i] 为山顶的山形数组长度为：
$$pre[i]+suf[i]?1$$
我们枚举所有的 nums[i]，计算所有的最长山顶数组长度 maxLen，最后需要删除的数组元素长度为 n - maxLen 即为最后需要返回的答案。

最长递增子序列

如何计算 pre 和 suf ？

pre 和 suf 的计算过程类似。先来看一下 pre 的计算。维护数组 pre，pre[i] 表示以 nums[i] 作为结尾的最长递增子序列的长度；维护辅助数组 g，表示以当前元素 nums[i] 结尾的最长递增子序列数组。

遍历数组 nums，当前遍历的元素为 nums[i] 记为 x，在数组 g 中使用二分查找找到第一个大于 x 的元素，对应的位置为 it - g.begin() + 1：

• 更新 pre[i] = it - g.begin() + 1；
• 如果 x 不在 g 中，则将 x 加入 g；否则将 x 更新到 g 中相应的位置。

在 suf 的计算过程中，我们从后往前遍历数组 nums，就是找最长的递增子序列，于是计算过程和 pre 的计算类似。

remark1：因为山峰不可能在数组首和尾两个位置出现，那么在遍历所有山峰的范围 [0, n-1] 时，需要先做判断 pre[i] >= 2 && suf[i] >= 2。

remark2：可以先计算 suf，然后一起计算 pre 和更新答案的，留给读者自己实现。

算法

class Solution {
public:
    int minimumMountainRemovals(vector<int>& nums) {
        int n = nums.size();
        vector<int> pre(n), g;
        for (int i = 0; i < n; ++i) {
            int x = nums[i];
            auto it = lower_bound(g.begin(), g.end(), x);
            pre[i] = it - g.begin() + 1;
            if (it == g.end()) {
                g.push_back(x);
            }
            else {
                *it = x;
            }
        }

        vector<int> suf(n);
        g.clear();
        for (int i = n - 1; i >= 0; --i) {
            int x = nums[i];
            auto it = lower_bound(g.begin(), g.end(), x);
            suf[i] = it - g.begin() + 1;
            if (it == g.end()) {
                g.push_back(x);
            }
            else {
                *it = x;
            }
        }

        int mx = 0;
        for (int i = 1; i < n - 1; ++i) {
            mx = max(mx, pre[i] + suf[i] - 1);
        }
        return n - mx;
    }
};

复杂度分析

时间复杂度：$O(nlogn)$，更新 pre 和 suf 的时间复杂度都为 O(nlogn)，更新答案的时间复杂度为 $O(n)$。

空间复杂度：$O(n)$，额外占用的空间为数组 pre、suf 和 g。空间复杂度：$O(n)$，额外占用的空间为数组 pre、suf 和 g。

---

写在最后

如果您发现文章有任何错误或者对文章有任何疑问，欢迎私信博主或者在评论区指出 💬💬💬。

如果大家有更优的时间、空间复杂度的方法，欢迎评论区交流。

最后，感谢您的阅读，如果有所收获的话可以给我点一个 👍 哦。