最大宽度坡

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

相关推荐

1 收藏 评论
分享
牛客网
牛客企业服务