文章目錄

• • 1. 題目
  • 2. 解題
  • • 2.1 n^2 解法
    • 2.2 nlogn 解法

197 / 1891，前10.4%

435 / 6154，前7.07%

前三題如下：

LeetCode 5557. 最大重復子字符串
LeetCode 5558. 合并兩個鏈表
LeetCode 5560. 設計前中后隊列（deque）

1. 題目

我們定義 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示例 4： 輸入：nums = [1,2,3,4,4,3,2,1] 輸出：1提示： 3 <= nums.length <= 1000 1 <= nums[i] <= 10^9 題目保證 nums 刪除一些元素后一定能得到山形數組。

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/minimum-number-of-removals-to-make-mountain-array
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

2. 解題

可以參考：

動態規劃應用–最長遞增子序列 LeetCode 300

• 計算每個位置處的最長上升子序長度
• 正反雙向計算2次
• 然后遍歷每個位置，計算 $min(n?l1?l2+1)$

2.1 n^2 解法

class Solution { public:int minimumMountainRemovals(vector<int>& nums) {int n = nums.size();vector<int> dp1(n, 1), dp2(n, 1);for(int i = 1; i < n; ++i){for(int j = i-1; j >= 0; --j){if(nums[j] < nums[i])dp1[i] = max(dp1[i], dp1[j]+1);}}for(int i = n-2; i >= 0; --i){for(int j = i+1; j < n; ++j){if(nums[j] < nums[i])dp2[i] = max(dp2[i], dp2[j]+1);}}int ans = INT_MAX;for(int i = 1; i < n-1; ++i){if(dp1[i]>1 && dp2[i]>1)ans = min(ans, n-(dp1[i]+dp2[i]-1));}return ans;} };

444 ms 12.2 MB C++

2.2 nlogn 解法

參考評論區：Zhenghao-Liu

采用了二分查找的方法，直接找到當前數字該插入的位置

直接復制過來Zhenghao-Liu大佬的代碼，如下：

const int MAXN=1000; int l2r[MAXN]; int r2l[MAXN]; const int INF=0x3f3f3f3f; class Solution { public:int minimumMountainRemovals(vector<int>& nums) {int size=nums.size();memset(l2r,0x3f,sizeof(l2r));memset(r2l,0x3f,sizeof(r2l));vector<int> vec;vec.reserve(size);for (int i=0;i<size;++i){int cur=nums.at(i);auto pos=lower_bound(vec.begin(),vec.end(),cur);if (pos==vec.end())vec.push_back(cur);else*pos=cur;l2r[i]=vec.size();}vec.clear();for (int i=size-1;i>=0;--i){int cur=nums.at(i);auto pos=lower_bound(vec.begin(),vec.end(),cur);if (pos==vec.end())vec.push_back(cur);else*pos=cur;r2l[i]=vec.size();}int ans=INF;for (int i=1;i<size-1;++i){int l=l2r[i];int r=r2l[i];if (l>1 && r>1)ans=min(ans,size-(l+r-1));}return ans;} };

56 ms 11.9 MB C++

---

我的CSDN博客地址 https://michael.blog.csdn.net/

長按或掃碼關注我的公眾號（Michael阿明），一起加油、一起學習進步！

總結

以上是生活随笔為你收集整理的LeetCode 1671. 得到山形数组的最少删除次数（最长上升子序DP nlogn）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。