作者sixB (6B)
看板Marginalman
标题Re: [闲聊] 每日leetcode
时间Thu Oct 31 00:59:36 2024
※ 引述《dont (dont)》之铭言：
: 1671. Minimum Number of Removals to Make Mountain Array
: ## 思路
嗯嗯差不多
大家想的都跟我一样
虽然我没有很认真看
严格山
山顶往左递减
往右也递减
##
左边扫过去右边扫过来
对每个index记他的level
lv意思是以这个点当山顶有多高
就是前面可以留几ㄍ
同lv更新成最小的number
我都会忘记可以用lower_bound
不过len < 1000
有没有二分搜没什麽差的感觉
最後再check要删几个
长度 - lv
class Solution {
public:
int minimumMountainRemovals(vector<int>& nums) {
// find peak
// left wing, right wing
// scan from both side to another
int n = nums.size();
vector<int> inc(n, 0), dec(n, 0); //increase, decrease
vector<int> level;
level.push_back(nums[0]);
for(int i = 1; i < n; i++){
int lv = ranges::lower_bound(level, nums[i]) - level.begin();
inc[i] = lv;
if(lv == level.size()){
level.push_back(nums[i]);
}
else if(level[lv] > nums[i]){
level[lv] = nums[i];
}
}
level.resize(0);
level.push_back(nums[n-1]);
for(int i = n-1 - 1; i >= 0; i--){
int lv = ranges::lower_bound(level, nums[i]) - level.begin();
dec[i] = lv;
if(lv == level.size()){
level.push_back(nums[i]);
}
else if(level[lv] > nums[i]){
level[lv] = nums[i];
}
}
int res = INT_MAX;
for(int i = 1; i < n - 1; i++){
if(inc[i] and dec[i]) res = min(res, (i - inc[i]) + (n - 1 - i - dec[i]) );
}
return res;
}
};
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 118.231.153.172 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Marginalman/M.1730307579.A.BE6.html