代码随想录算法训练营第五十九天|503.下一个更大元素II、42. 接雨水

​

LeetCode 503 下一个更大元素II

题目链接：https://leetcode.cn/problems/next-greater-element-ii/

思路：

方法一:两个for循环遍历单调栈

第一个for循环确定数组中的某个值在右边有最大的数，第二个for循环是为了可以使数组变成循环数组
例子：[5,4,3,2,1]
1、栈里 4,3,2,1,0](右边为栈顶，栈内元素为下标）
2、从下标0开始再次循环
(模拟一次就目标了）

代码：

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(); i++){if(nums[i] <= nums[st.top()])st.push(i);else{while(!st.empty() && nums[i] > nums[st.top()]){result[st.top()] = nums[i];st.pop();}st.push(i);}}for(int i = 0; i < nums.size(); i++){if(nums[i] <= nums[st.top()])st.push(i);else{while(!st.empty() && nums[i] > nums[st.top()]){result[st.top()] = nums[i];st.pop();}st.push(i);}}return result;}
};

方法二:单调栈，用取模的方法对数组进行循环

代码

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()])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;}
};

总结

关键在于如何循环数组

---

LeetCode 42 接雨水

题目链接：https://leetcode.cn/problems/trapping-rain-water/

思路：

本题关键点：

1. 接雨水重点在于要找当前元素左边第一个比它的元素和右边第一个比它大的元素
2. 接雨水是按行来计算的
   
3. 明确h和w是如何计算的，w在计算中必须还要减1

代码

class Solution {
public:int trap(vector<int>& height) {int result = 0;stack<int>st;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[i], height[st.top()]) - height[mid];int w = i - st.top() - 1;result += h * w;}}st.push(i);}}return result;}
};

总结

接雨水问题是经典问题，后续要多加练习

---

今日总结：

还有一天，加油！