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 变成 山形状数组 的​ 最少 删除次数。

示例 1：

**输入：** nums = [1,3,1]
**输出：** 0
**解释：** 数组本身就是山形数组，所以我们不需要删除任何元素。

示例 2：

**输入：** nums = [2,1,1,5,6,2,3,1]
**输出：** 3
**解释：** 一种方法是将下标为 0，1 和 5 的元素删除，剩余元素为 [1,5,6,3,1] ，是山形数组。

提示：

• 3 <= nums.length <= 1000
• 1 <= nums[i] <= 109
• 题目保证 nums 删除一些元素后一定能得到山形数组。

灵神视频

[TOC]

思路

山形数组可以拆分成一段上升和一段下降，求最少操作次数，因此可以转换为求最长的上升和下降子序列。因此可以想到求以nums[i]为结尾的最长上升子序列和以nums[i]为开始的最长下降子序列，两者结合即为山形数组。

Code

• 时间复杂度: O(n^2)

• 空间复杂度: O(n)

  []

  class Solution {
  public:
      int minimumMountainRemovals(vector<int>& nums) {
        int n = nums.size(), increment[n], decrement[n];
  
        for (int i = 0; i < n; i ++) {
          increment[i] = 1;
          for (int j = 0; j < i; j ++) {
            if (nums[i] > nums[j]) {
              increment[i] = max(increment[i], increment[j] + 1);
            }
          }
        }
        int ans = 0;
        for (int i = n - 1; i >= 0; i --) {
          decrement[i] = 1;
          for (int j = i + 1; j < n; j ++) {
            if (nums[i] > nums[j]) {
              decrement[i] = max(decrement[i], decrement[j] + 1);
            }
          }
          // if(i != n - 1 && i) ans = max(ans, increment[i] + decrement[i] - 1);
        }
        for (int i = 1; i < n - 1; i ++) {
          if (increment[i] != 1 && decrement[i] != 1)
            ans = max(ans, increment[i] + decrement[i] - 1);
          // cout << "i:" << i << "  inc[i]:" << increment[i] << "  dec[i]:" << decrement[i] << endl;
        }
        return n - ans;
      }
  };

Code

• 时间复杂度: O(nlogn)

• 空间复杂度: O(n)

  []

  class Solution {
  public:
      int minimumMountainRemovals(vector<int>& nums) {
        // O(nlogn)
        int n = nums.size();
        vector<int> inc, dec;
        vector<int> finc(n), fdec(n);
        for(int i = 0; i < n; i ++) {
          int idx = lower_bound(inc.begin(), inc.end(), nums[i]) - inc.begin();
          if (idx == inc.size()) {
            inc.push_back(nums[i]);
          } else {
            inc[idx] = nums[i];
          }
          finc[i] = idx + 1;
        }
  
        for(int i = n - 1; i >= 0; i --) {
          int idx = lower_bound(dec.begin(), dec.end(), nums[i]) - dec.begin();
          if (idx == dec.size()) {
            dec.push_back(nums[i]);
          } else {
            dec[idx] = nums[i];
          }
          fdec[i] = idx + 1;
        }
  
        int ans = 0;
        for (int i = 1; i < n - 1; i ++) {
          if (finc[i] != 1 && fdec[i] != 1)  // 必须要有山形结构，峰顶下标不能是0或者n-1
            ans = max(ans, finc[i] + fdec[i] - 1);
          // cout << "i:" << i << "  inc[i]:" << increment[i] << "  dec[i]:" << decrement[i] << endl;
        }
        return n - ans;
  
  };