第五十九天|503. 下一个更大元素 II 42. 接雨水

本文主要是介绍第五十九天|503. 下一个更大元素 II 42. 接雨水，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

503. 下一个更大元素

就是遍历两遍

class Solution {
public:vector<int> nextGreaterElements(vector<int>& nums) {vector<int> res(nums.size(),-1);stack<int> st;for(int i=0;i<2*nums.size();i++){while(!st.empty()&&nums[i%nums.size()]>nums[st.top()]){res[st.top()]=nums[i%nums.size()];st.pop();}st.push(i%nums.size());}return res;}
};

42. 接雨水

双指针做法是竖向求每一格的雨水

class Solution {
public:int trap(vector<int>& height) {int res=0;vector<int> maxLeft(height.size(),0);vector<int> maxRight(height.size(),0);for(int i=1;i<height.size();i++){maxLeft[i]=max(height[i-1],maxLeft[i-1]);}for(int i=height.size()-2;i>=0;i--){maxRight[i]=max(height[i+1],maxRight[i+1]);}for(int i=1;i<height.size()-1;i++){if(min(maxLeft[i],maxRight[i])-height[i]>0)res+=min(maxLeft[i],maxRight[i])-height[i];}return res;}
};

其实与其说是双指针不如说是 双数组法

单调栈是横向求雨水

class Solution {
public:int trap(vector<int>& height) {int res=0;stack<int> st;for(int i=0;i<height.size();i++){while(!st.empty()&&height[i]>height[st.top()]){int mid=st.top();st.pop();if(!st.empty())res+=(min(height[st.top()],height[i])-height[mid])*(i-st.top()-1);}st.push(i);}return res;}
};

要注意这句if(!st.empty())

这篇关于第五十九天|503. 下一个更大元素 II 42. 接雨水的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---