最大宽度坡
https://leetcode.cn/problems/maximum-width-ramp/description/
这题要我们找到最大坡度,就是i下标后面那个数比它大,且j-i的值要最大。根据单调栈我们可以设置一个单调递减的栈,这样我们可以把可以是坡底的下标压入栈,然后我们在从前往后遍历,让j-i的值可以最大
stack<int> p;// 存储索引的单调递减栈
int n=nums.size();
//从左到右遍历数组,构建单调递减栈
for(int i=0;i<n;i++)
{
// 如果栈为空,或者当前元素小于等于栈顶元素对应的值,则压入栈
if(p.empty()||nums[p.top()]>nums[i])
{
p.push(i);
}
}
int ans=0;
for(int i=n-1;i>=0;i--)
{
// 当栈不为空,且当前元素大于等于栈顶元素对应的值时,找到了一个坡底找到坡顶
while(!p.empty()&&nums[i]>=nums[p.top()])
{
ans=max(ans,i-p.top());
p.pop();
}
}
return ans;
}
#7月23#