本文主要是介绍代码随想录Day61 | 503. 下一个更大元素 II | 42. 接雨水，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
503. 下一个更大元素 II
class Solution {
public:vector<int> nextGreaterElements(vector<int>& nums) {stack<int> st;int n = nums.size();vector<int> res(n,-1);for(int i=0;i<n*2;i++){ //达成循环效果while(st.size()&&nums[st.top()%n]<nums[i%n]){res[st.top()%n]=nums[i%n];st.pop();}st.push(i);}return res;}
};42. 接雨水
暴力法(最后一个用例超时）
class Solution {
public:int trap(vector<int>& height) {int n=height.size();int sum=0;for(int i=0;i<n;i++){ //按列计算每列的雨水量，并累加（暴力法）if(i==0||i==n-1) continue; //不求首尾的雨水int rHeight = height[i]; // 记录右边柱子的最高高度int lHeight = height[i]; // 记录左边柱子的最高高度for (int r = i + 1; r < n; r++) {rHeight = max(rHeight,height[r]);}for (int l = i - 1; l >= 0; l--) {lHeight = max(lHeight,height[l]);}int h = min(lHeight,rHeight)-height[i];if(h>0)sum+=h;}return sum;}
};暴力优化法(双指针）
class Solution {
public:int trap(vector<int>& height) {int n = height.size();if(n<=2) return 0;vector<int> lmaxh(n,0);vector<int> rmaxh(n,0); //把两边的最高的柱子用数组存起来，以空间换时间lmaxh[0]=height[0];int sum=0;for(int i=1;i<n;i++){lmaxh[i] = max(height[i],lmaxh[i-1]);}rmaxh[n-1] = height[n-1];for(int i=n-2;i>=0;i--){rmaxh[i] = max(height[i],rmaxh[i+1]);}for(int i=0;i<n;i++){if(i==0||i==n-1) continue;int h = min(rmaxh[i],lmaxh[i])-height[i];if(h>0)sum+=h;}return sum;}
};单调栈法
class Solution {
public:int trap(vector<int>& height) {stack<int> st; //存储下标int n = height.size();int sum=0;for(int i=0;i<n;i++){if(st.size()&&height[i]<height[st.top()]){st.push(i);}if(st.size()&&height[i]==height[st.top()]){st.pop();st.push(i);}else{while(st.size()&&height[i]>height[st.top()]){int mid = st.top();st.pop();if(st.size()){int h = min(height[st.top()],height[i])-height[mid];int w = i-st.top()-1;sum+=h*w;}}st.push(i);}}return sum;}
};这篇关于代码随想录Day61 | 503. 下一个更大元素 II | 42. 接雨水的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
