LeetCode 5559. 得到山形数组的最少删除次数
原题链接
困难
算法
(二分) $O(n\log n)$
- 顶峰的左边是一段连续的子序列,并且是递增的子序列;顶峰的右边是一段连续的子序列,并且是递减的子序列。
- 显然最少删除次数,就是让左右的子序列越长越好。
- 那么我们用最长上升子序列算法 $O(n\log n)$ 算出以每个元素为右端点的最长上升子序列长度
ls[i]
,和以每个元素为左端点的最长下降组序列长度 rs[i]
,答案就是最小的 n - 1 - ls[i] - rs[i]
。
C++ 代码
class Solution {
public:
int minimumMountainRemovals(vector<int>& a) {
int n = a.size();
vector<int> ls(n, 0), rs(n, 0), dp(n, 0x3f3f3f3f);
for(int i = 0; i < n; ++i) {
int p = lower_bound(dp.begin(), dp.end(), a[i]) - dp.begin();
dp[p] = a[i];
ls[i] = p;
}
fill(dp.begin(), dp.end(), 0x3f3f3f3f);
for(int i = n - 1; i >= 0; --i) {
int p = lower_bound(dp.begin(), dp.end(), a[i]) - dp.begin();
dp[p] = a[i];
rs[i] = p;
}
int ans = n;
for(int i = 1; i < n - 1; ++i) {
ans = min(ans, n - 1 - ls[i] - rs[i]);
}
return ans;
}
};