本文主要是介绍力扣962.最大宽度坡,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
力扣962.最大宽度坡
-
单调栈
- 栈中存从nums[0]开始的一个单调下降的序列
- 为了让坡的底尽量小
- 然后倒序遍历nums,找符合条件的栈中元素 弹出
- 栈中存从nums[0]开始的一个单调下降的序列
-
class Solution {public:int maxWidthRamp(vector<int>& nums) {int n = nums.size();int res = 0;stack<int> st;for(int i=0;i<n;i++)if(st.empty() || nums[st.top()] > nums[i])st.emplace(i);for(int i=n-1;i>=0;i--){while(!st.empty() && nums[st.top()] <= nums[i]){int t = st.top();st.pop();res = max(res,i - t);}}return res;}};
参考题解:https://leetcode.cn/problems/maximum-width-ramp/solutions/666604/zui-da-kuan-du-po-dan-diao-zhan-cun-de-s-myj9/
这篇关于力扣962.最大宽度坡的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!