Re: [閒聊] 每日leetcode
題目:
給你一個陣列
移除最少元素讓陣列變成一座嚴格的山
思路:
嚴格山
=從左右兩邊都是嚴格遞增
=要lis兩次
開頭結尾 或是lis==1都不可以
然後每個數字都看看他是多少
選最小就好了
```cpp
class Solution {
public:
int minimumMountainRemovals(vector<int>& nums)
{
int n = nums.size();
vector<int> l2r(n,0);
vector<int> r2l(n,0);
vector<int> st;
for(int i = 0 ; i < n ; i ++)
{
if(st.empty() || nums[i] > st[st.size()-1])
{
st.push_back(nums[i]);
l2r[i] = st.size();
continue;
}
int l = 0 ;
int r = st.size();
int m = (l+r)/2;
while(l<=r)
{
m = (l+r)/2;
if(st[m] >= nums[i])
{
r = m-1;
}
else if(st[m] < nums[i])
{
l = m+1;
}
}
st[l] = nums[i];
l2r[i] = st.size();
}
st.clear();
for(int i = n-1 ; i >= 0 ; i --)
{
if(st.empty() || nums[i] > st[st.size()-1])
{
st.push_back(nums[i]);
r2l[i] = st.size();
continue;
}
int l = 0 ;
int r = st.size();
int m = (l+r)/2;
while(l<=r)
{
m = (l+r)/2;
if(st[m] >= nums[i])
{
r = m-1;
}
else if(st[m] < nums[i])
{
l = m+1;
}
}
st[l] = nums[i];
r2l[i] = st.size();
}
int res = INT_MAX;
for(int i = 1 ; i < n-1 ; i ++)
{
if(l2r[i] == 1 || r2l[i] == 1)continue;
res = min(res, n-l2r[i]-r2l[i]+1);
}
return res;
}
};
```
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 49.216.24.187 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1730274294.A.622.html
→
10/30 15:50,
1年前
, 1F
10/30 15:50, 1F
推
10/30 15:52,
1年前
, 2F
10/30 15:52, 2F
推
10/30 16:13,
1年前
, 3F
10/30 16:13, 3F
推
10/30 21:35,
1年前
, 4F
10/30 21:35, 4F
討論串 (同標題文章)
完整討論串 (本文為第 1061 之 1548 篇)：