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

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

题目描述：

我们定义 arr 是 山形数组 当且仅当它满足：

• arr.length >= 3

• 存在某个下标 i（从 0 开始） 满足 0 < i < arr.length - 1

  且：

  • arr[0] < arr[1] < ... < arr[i - 1] < arr[i]
• arr[i] > arr[i + 1] > ... > arr[arr.length - 1]

给你整数数组 nums ，请你返回将 nums 变成 山形状数组 的 最少 删除次数。

数据范围：

$3\le nums.len \le 1000, 1\le nums[i] \le 10^9$

题解：

可以发现是一个单调上升子序列问题，而且是严格上升。只需要找一下以每个位置结尾的单调上升子序列的长度即可。

刚好可以左边一遍，右边一遍。

可以选择使用二分的做法， $dp[len]$ 表示长度为 $len$ 的子序列末尾最小数字，然后对于 $nums[i]$ 如果可以直接接在 $dp[len]$ 末尾，那么就 dp[++len] = nums[i]。不能接的话说明 $nums[i] < dp[len]$ ，可以从前面找出来末尾字符比 $nums[i]$ 大的，使用 $lower\_bound(dp + 1, dp + 1 + len + 1, nums[i])$ 找到下标 $index$ ，然后修改长度为 $index$ 的末尾数字为 $nums[i]$ 。

最后需要注意的是，最后的数组的长度要大于等于 $3$ ，而且需要满足，山峰不在左右端点处，因此需要判断 $left[i] > 1$ ， $right[i] > 1$ 。

代码：

auto optimize_cpp_stdio = []()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    return 0;
}();
class Solution
{
public:
    const static int maxn = 1e5 + 10;
    const static int maxm = 1e5 + 10;
    const int INF = 0x3f3f3f3f;
    int minimumMountainRemovals(vector<int> &nums)
    {
        int n = nums.size();
        vector<int> left(n), right(n);
        vector<int> a(n);
        // dp[n] 长度为 n 的末尾下标是哪个
        a[0] = nums[0];
        int len = 1;
        left[0] = len;
        for (int i = 1; i < n; ++i)
        {
            if (nums[i] > a[len - 1])
                a[len++] = nums[i];
            else
            {
                int index = lower_bound(a.begin(), a.begin() + len, nums[i]) - a.begin();
                a[index] = nums[i];
            }
            left[i] = len;
        }

        len = 1;
        right[n - 1] = len;
        a[0] = nums[n - 1];
        for (int i = n - 2; i >= 0; --i)
        {
            if (nums[i] > a[len - 1])
                a[len++] = nums[i];
            else
            {
                int index = lower_bound(a.begin(), a.begin() + len, nums[i]) - a.begin();
                a[index] = nums[i];
            }
            right[i] = len;
        }
        int ans = n;
        for (int i = 1; i < n - 1; ++i)
        {
            if (left[i] > 1 && right[i] > 1)
            {
                ans = min(ans, n - left[i] - right[i] + 1);
            }
        }
        return ans;
    }
};