acytoo

Leetcode 1671 Minimum Number of Removals to Make Mountain Array

这道题像是一道双DP的题，记录每个位置分别是删与不删，或者是否是转折点，或者这个点属于上升段还是下降段，所需要删除的元素数，最后就能得到答案。以前做过好几道类似的题目，记录两种状态，然后取其中最优解。这就是刷完题却不怎么复习的弊端了，记个大概。但是这也体现力刷题的好处：遇到一道题，你能很快找出一个大概思路，接下来就是完成代码，submit，debug。

这道题我们选用每个元素作为顶点时的最长array作为DP的依据，每个元素两侧的数值分别计算。算是双DP的变种吧。

static int x = [] () {ios::sync_with_stdio(false); cin.tie(0); return 0;} ();
class Solution {
 public:
  int minimumMountainRemovals(vector<int>& nums) {
    const int n = nums.size();
    vector<int> l(n, 1), r(n, 1); // l: 第i个元素作为顶点时，左侧的元素个数
    for (int i = 0; i < n; ++i)
      for (int j = 0; j < i; ++j)
        if (nums[j] < nums[i])
          l[i] = max(l[i], l[j] + 1);
    for (int i = n - 1; i >= 0; --i)
      for (int j = n - 1; j > i; --j)
        if (nums[i] > nums[j])
          r[i] = max(r[i], r[j] + 1);
    int res = n;
    for (int i = 0; i < n; ++i) {
      if (l[i]  == 1 || r[i] == 1) continue;
      res = min(res, n - (l[i] + r[i] - 1));
    }
    return res;
  }
};

这么熟悉的套路，LeetCode还是给分了一个hard，真是越来越水了。

#直达链接

LeetCode 1671. Minimum Number of Removals to Make Mountain Array

相关文章：