本文主要是介绍代码随想录算法训练营第六十二天|503.下一个更大元素Ⅱ、42.接雨水，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
文档链接：https://programmercarl.com/
LeetCode503.下一个更大元素Ⅱ
题目链接：https://leetcode.cn/problems/next-greater-element-ii/
思路：乍一看跟下一个更大元素Ⅰ没什么不同，无非就是本题要循环数组了。
想法一：直接拼接一个nums在后面，遍历就可以了。
想法二：假装拼接一个，想法很巧妙。
单调栈：
class Solution {
public:vector<int> nextGreaterElements(vector<int>& nums) {vector<int> result(nums.size(), -1);stack<int> st;st.push(0);for(int i = 1; i < nums.size() * 2; i++) {if(nums[i % nums.size()] <= nums[st.top()]) {if(!st.empty())st.push(i % nums.size());} else {while(!st.empty() && nums[i % nums.size()] > nums[st.top()]) {result[st.top()] = nums[i % nums.size()];st.pop();}st.push(i % nums.size());}}return result;}
};LeetCode42.接雨水
题目链接：https://leetcode.cn/problems/trapping-rain-water/
思路：单调栈是按行来计算的。
暴力推荐按列计算。
暴力：
class Solution {
public:int trap(vector<int>& height) {int sum = 0;for(int i = 0; i < height.size(); i++) {if(i == 0 || i == height.size() - 1) continue;int lHeight = height[i];int rHeight = height[i];for(int j = i + 1; j < height.size(); j++) {if(height[j] > rHeight) rHeight = height[j];}for(int j = i - 1; j >= 0; j--) {if(height[j] > lHeight) lHeight = height[j];}int h = min(lHeight, rHeight) - height[i];sum += h;}return sum;}
};单调栈：
class Solution {
public:int trap(vector<int>& height) {stack<int> st;int sum = 0;st.push(0);for(int i = 1; i < height.size(); i++) {if(height[i] <= height[st.top()]) {st.push(i);} else {while(!st.empty() && height[i] > height[st.top()]) {int mid = st.top(); st.pop();if(!st.empty()) {int h = min(height[st.top()], height[i]) - height[mid];int w = i - st.top() - 1;sum += h * w;}}st.push(i);}}return sum;}
};总结：补
这篇关于代码随想录算法训练营第六十二天|503.下一个更大元素Ⅱ、42.接雨水的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
