作者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/m.aspx?n=bbs/Marginalman/M.1730307579.A.BE6.html