503. Next Greater Element II#
503. Next Greater Element II - LeetCode
Problem Analysis#
This is a problem that is almost the same as "739. Daily Temperatures", but it is changed to a circular array. Therefore, after the first traversal of all array elements, it needs to be traversed again from the beginning (index 0) to simulate the loop. During the second traversal, the target value is searched for the elements that do not have a larger value on the right side in the first traversal, so there is no need to push into the stack when the traversed element is not greater than the stack element.
Code Implementation#
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. Trapping Rain Water#
42. Trapping Rain Water - LeetCode
At first, I thought that I needed to use the maximum value as the dividing line. When traversing the left side of the maximum value, I needed to find the first larger number after the current traversed element, which means I needed to maintain an increasing monotonic stack. The traversal on the right side of the maximum value is the opposite. But after writing it, I found that it was not the case. For example, for the data [2,1,0,1,3], if I maintain an increasing monotonic stack, how can I calculate the amount of rainwater. I also thought that I could maintain a decreasing monotonic stack first, and then maintain an increasing monotonic stack, and continuously traverse this as an interval, but it is not easy to implement. Moreover, in both of my ideas, the rainwater volume is calculated by accumulating the rainwater that each pillar can hold (by column), which adds complexity.
Problem Analysis#
To calculate the amount of rainwater in the concave groove, you need to know the middle pillar, the left high pillar, and the right high pillar, and then calculate it using the length times width method.
During the process of maintaining the monotonic stack, when the traversed element is greater than the top element of the stack, it is necessary to calculate the amount of rainwater. At this time, the top element of the stack is the middle pillar, the traversed element is the right high pillar, and the left high pillar is just the top element of the stack after popping out the top element (middle pillar).
When the traversed element is equal to the top element of the stack, the operation of popping out the top element is optional. If it is not popped out, the calculation will be performed for the equal pillars, but the calculated height of the rainwater for the pillars in the stack with equal pillars is 0.
Code Implementation#
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;
}
};