最大宽度坡

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#
全部评论

相关推荐

不愿透露姓名的神秘牛友
昨天 11:16
点赞 评论 收藏
分享
下北澤大天使:你是我见过最美的牛客女孩😍
点赞 评论 收藏
分享
半解316:内容充实,细节需要修改一下。 1,整体压缩为一页。所有内容顶格。 2,项目描述删除,直接写个人工作量 修改完之后还需要建议,可以私聊
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务