我的速度应该是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;
}
};
```