我的速度應該是n logn 剛剛看了On 感覺 好屌 我室友的解法更特別一點 也是On 他開10000格的陣列然後在上面DP 只剩我n log n了 題目: 請問最長的nums[i] nums[j] 在i<j 並且 nums[i] < nums[j]的情況下 是多長 思路: 因為越左邊而且更小的數字一定更好 所以就會用到monotonic stack 來記錄遞減的數字跟他們的index 然後有更大的數字的時候 就要回去找 回去找的時候 因為是遞減 所以二分搜可以套用在這裡 就找到了 姆咪 ```cpp class Solution { public: int maxWidthRamp(vector<int>& nums) { int res = 0; int n = nums.size(); vector<pair<int,int>> sta; for(int i = 0 ; i < n ; i ++) { if(sta.empty() || sta.back().first > nums[i]) { sta.push_back({nums[i],i}); continue; } int l = 0 ; int r = sta.size(); while(l<=r) { int m = (l+r)/2; int mval = sta[m].first; if(mval <= nums[i]) { r = m-1; } else { l = m+1; } } res = max(res , i - sta[l].second); } return res; } }; ``` -- ※ 發信站: 批踢踢實業坊(web-ptt.org.tw), 來自: 101.12.20.111 (臺灣) ※ 文章網址: https://web-ptt.org.tw/Marginalman/M.1728559107.A.DC5

推 kirisan: 你好爛 10/10 19:19

噓 mrsonic: 有得放假還在刷 我好討厭你 10/10 19:19