原文链接: https://leetcode-cn.com/problems/minimum-number-of-removals-to-make-mountain-array

英文原文

You may recall that an array arr is a mountain array if and only if:

• arr.length >= 3
• There exists some index i (0-indexed) with 0 < i < arr.length - 1 such that:
  • arr[0] < arr[1] < ... < arr[i - 1] < arr[i]
  • arr[i] > arr[i + 1] > ... > arr[arr.length - 1]

Given an integer array nums​​​, return the minimum number of elements to remove to make nums​​​ a mountain array.

 

Example 1:

Input: nums = [1,3,1]
Output: 0
Explanation: The array itself is a mountain array so we do not need to remove any elements.

Example 2:

Input: nums = [2,1,1,5,6,2,3,1]
Output: 3
Explanation: One solution is to remove the elements at indices 0, 1, and 5, making the array nums = [1,5,6,3,1].

Example 3:

Input: nums = [4,3,2,1,1,2,3,1]
Output: 4

Example 4:

Input: nums = [1,2,3,4,4,3,2,1]
Output: 1

 

Constraints:

• 3 <= nums.length <= 1000
• 1 <= nums[i] <= 109
• It is guaranteed that you can make a mountain array out of nums.

中文题目

我们定义 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 = [4,3,2,1,1,2,3,1]
输出：4

提示：

输入：nums = [1,2,3,4,4,3,2,1]
输出：1

 

提示：

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

通过代码

高赞题解

思路：$O(n^2)$预处理，$O(n)$计算答案

• 枚举每一个位置作为山形最高点，就需要计算该位置的左右两边最少需要删除多少个点。
• 以计算左边为例，要计算位置i左边最少删除个数delleft[i]，就要从i-1的位置向左遍历（指针记为j）直到头，每当遇到nums[j] < nums[i]的位置j，就用以下两个情况的最小值更新delleft[i]的答案
  • delleft[i]，表示保留原始情况，不更新
  • delleft[j] + i - j - 1，表示利用 delleft[j]的结果再加上夹在j和i之间所有的点都删除的总数
• 类似地处理每个元素右边最少删除个数delright
• 该处理的复杂度为$O(n^2)$，之后同时遍历delleft和delright，返回最小delleft[i] + delright[i]
• 细节见代码
• 备注：比赛时没想太多，直接$O(n^2)$过的，事实上还有$O(nlogn)$的解法，具体可以关注一下这道题：300.最长上升子序列

  class Solution {
  public:
      int minimumMountainRemovals(vector<int>& nums) {
          int n = nums.size();
          vector<int> delleft(n), delright(n);
          for(int i = 0; i < n; ++i){ // 初始化delleft和delright为其左边或右边点的个数
              delleft[i] = i;
              delright[i] = n - i - 1;
          }
          for(int i = 0; i < n; ++i){
              for(int j = i - 1; j >= 0; --j){
                  if(nums[j] < nums[i]) 
                      delleft[i] = min(delleft[i], delleft[j] + i - j - 1);
              }
          }
          for(int i = n - 1; i >= 0; --i){
              for(int j = i + 1; j < n; ++j){
                  if(nums[j] < nums[i]) 
                      delright[i] = min(delright[i], delright[j] + j - i - 1);
              }
          }
          int ans = INT_MAX;
          for(int i = 1; i < n - 1; ++i){ // 注意数组两头的元素不能作为山顶
              if(delleft[i] == i || delright[i] == n - i - 1) continue; // 某点左边或者右边全删除完的不能作为山顶
              ans = min(ans, delleft[i] + delright[i]);
          }
          return ans;
      }
  };

统计信息

通过次数	提交次数	AC比率
2168	4630	46.8%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言