503. 下一个更大元素 II#
503. 下一个更大元素 II - 力扣（Leetcode）
问题分析#
几乎和「739. 每日温度」一样的一道题目，但却改成了循环数组，所以在第一次遍历完所有数组元素后，需要再从头（下标 ）遍历一次模拟循环。在第二次便利过程是为第一次遍历未找到右侧有更大值的元素查找目标值，所以不需要再在遍历元素不大于栈元素时入栈的操作。
代码实现#
class Solution {
public:
vector<int> nextGreaterElements(vector<int>& nums) {
vector<int> result(nums.size(), -1);
if (nums.size() == 1) return result;
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++) {
while (!st.empty() && nums[i] > nums[st.top()]) {
result[st.top()] = nums[i];
st.pop();
}
st.push(i);
}
return result;
}
};
42. 接雨水#
42. 接雨水 - 力扣（Leetcode）
一开始认为要以最大值为分界线，最大值左侧遍历时需要寻找当前遍历元素往后的第一个更大的数，也就是说需要维护一个递增单调栈；而最大值右侧遍历则与之相反。但写完发现并不是如此，如 这个数据如果维护一个单调递增栈，那么如何计算雨水量。又想可以先维护单调递减、再维护单调递增，以此为一个区间不断往后遍历，但实现起来也不简单。而且在我的两种思路中都是通过累加每个柱子可以承接的雨水量（按列）来计算，增加了复杂性。
问题分析#
要计算凹槽的雨水量，需要知道中间柱子、左高柱子、右高柱子三个，然后通过长乘宽的思路来计算。
在维护单调栈的过程中当遍历元素大于栈顶元素，此时就需要进行雨水量的计算。此时栈顶元素即为中间柱子，遍历元素即为右高柱子，而左高柱子则刚好是栈弹出栈顶元素（中间柱子）后的栈顶元素。
当遍历元素与栈顶元素相等时，弹出栈顶元素的操作是可选的，如果不弹出那么会对相等柱子都进行计算，只不过栈中还有与之相等的柱子时雨水的高计算结果为 。
代码实现#
class Solution {
public:
int trap(vector<int>& height) {
int result = 0;
if (height.size() <= 2) return result;
stack<int> st;
st.push(0);
for (int i = 1; i < height.size(); i++) {
if (height[i] < height[st.top()])
st.push(i);
else if (height[i] == height[st.top()]) {
st.pop();
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;
result += h * w;
}
}
st.push(i);
}
}
return result;
}
};