LeetCode503. 下一个更大元素II
题目链接：503. 下一个更大元素II
独上高楼，望尽天涯路
和昨天的那道题大部分是一个思路，对于循环数组，只需要遍历nums两遍即可。
class Solution {
public:
vector<int> nextGreaterElements(vector<int>& nums) {
stack<int> st;
vector<int> result(nums.size(), -1);
for (int i = 0; i < 2 * nums.size() - 1; i++) {
while (!st.empty() && nums[i % nums.size()] > nums[st.top()]) {
result[st.top()] = nums[i % nums.size()];
st.pop();
}
if (result[i % nums.size()] == -1) {
st.push(i % nums.size());
}
}
return result;
}
};
慕然回首，灯火阑珊处
思路一样。
LeetCode42. 接雨水
题目链接：42. 接雨水
独上高楼，望尽天涯路
经典题目，挖个坑，二刷的时候把所有方法都练会。
慕然回首，灯火阑珊处
一刷仅考虑单调栈解法，按照行方向计算雨水，下面这段话很形象的阐述了单调栈解法的思路。
因为一旦发现添加的柱子高度大于栈头元素了，此时就出现凹槽了，栈头元素就是凹槽底部的柱子，栈头第二个元素就是凹槽左边的柱子，而添加的元素就是凹槽右边的柱子。
class Solution {
public:
int trap(vector<int>& height) {
stack<int> st;
int sum = 0;
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()) {
int h = min(height[i], height[st.top()]) - height[mid];
int w = i - st.top() - 1;
sum += h * w;
}
}
st.push(i);
}
return sum;
}
};