Re: [閒聊] 每日leetcode
我的速度應該是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;
}
};
```
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 101.12.20.111 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1728559107.A.DC5.html
推
10/10 19:19,
1年前
, 1F
10/10 19:19, 1F
噓
10/10 19:19,
1年前
, 2F
10/10 19:19, 2F
討論串 (同標題文章)
完整討論串 (本文為第 970 之 1554 篇)：