題目: 給你一個陣列 移除最少元素讓陣列變成一座嚴格的山 思路: 嚴格山 =從左右兩邊都是嚴格遞增 =要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://webptt.com/m.aspx?n=bbs/Marginalman/M.1730274294.A.622.html