503 下一个更大元素 II
思路：我们对数组进行两次迭代（即2 * nums.size()次迭代）以模拟数组的循环性质。对于每个迭代，我们将当前元素与堆栈顶部的元素进行比较。如果当前元素大于堆栈顶部的元素，则表示我们已经找到了堆栈顶部元素的下一个更大的元素，因此我们相应地更新结果向量，并将元素从堆栈中弹出。我们重复此过程，直到堆栈为空或堆栈顶部的元素大于或等于当前元素为止。最后，我们将当前元素的索引推到堆栈上。
在迭代结束时，堆栈中剩余的任何元素右侧都没有更大的元素（因为我们已经两次迭代了数组），因此我们将它们对应的结果向量条目保留为-1。
1.单调栈
class Solution {
public:
vector<int> nextGreaterElements(vector<int>& nums) {
vector<int> result(nums.size(), - 1);
if(nums.size() == 0) return result;
stack<int> st;
for(int i = 0; i < nums.size() * 2; i++){
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;
}
};
42 接雨水
思路：该解决方案使用堆栈来跟踪可能形成水池的柱子的索引。我们从左到右遍历每个柱子，如果当前柱子高度小于等于堆栈顶部柱子的高度，将当前柱子的索引压入堆栈。如果当前柱子高度大于堆栈顶部柱子的高度，表示可能形成一个水池，我们弹出堆栈顶部柱子的索引，并计算从左边柱子到右边柱子之间的水平面积。水平面积可以通过当前堆栈顶部的柱子和当前柱子高度中的较小值减去弹出柱子的高度得出，并且该水平面积的宽度等于弹出柱子的索引和当前堆栈顶部的柱子索引之间的距离减去1。我们将所有的水平面积相加，即可得到捕获的雨水总量。
1.单调栈
class Solution {
public:
int trap(vector<int>& height) {
stack<int> st;
st.push(0);
int sum = 0;
for(int i = 1; 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[st.top()], height[i]) - height[mid];
int w = i - st.top() - 1;
sum += h * w;
}
}
st.push(i);
}
return sum;
}
};
