directory
-
- The title
- Train of thought
- Violence law
- Dynamic programming
- Double pointer method
- Monotonous stack
The title
Given n non-negative integers to represent the height diagram of each column of width 1, calculate how much rain the columns in this order can catch after rain.
Input: height = [0,1,0,2,1,0,1,3,2,1,2,1,1] output: 6
Example 2:
Height = [4,2,0,3,2,5
0 <= n <= 3 * 10^4 0 <= height[I] <= 10^5
Train of thought
For each element in the array, the highest water level is: the smaller value of the maximum height on both sides – the current height value is described in pseudocode: water[I] = min(left,right) -height [I]; (I didn’t expect to calculate each element. I thought I would find several higher points and then divide them into sections.) This simplifies the problem to finding the largest value to the right and the largest value to the left of each element. Didn’t think of this, I feel very difficult to do down.
Violence law
Use brute force method, for traversing the number group, the corresponding element to find the maximum value, along with the above idea: obviously time complexity is O(n^2)
class Solution {
public:
int trap(vector<int>& height)
{
int ans = 0;
int n = height.size(a);for(int i = 0; i < n; i++)
{
// find the maximum value
int left_max = 0, right_max = 0;
for(int j = i; j >= 0; j--)
left_max = max(left_max,height[j]);
for(int j = i; j < n; j++)
right_max = max(right_max,height[j]);
// Accumulate rainwater at this location
ans += min(left_max,right_max) - height[i];
}
returnans; }};Copy the codeDynamic programming
Previously, we found the maximum left and right values of each element as we walked through the element. It can be found in advance, stored, and consulted directly when calculating rain. You need to construct two arrays beforehand to store them. When populating a maximum array, remember that the left maximum of the current element is related only to the left maximum of the current element and the one on the left. Left_max [I] = Max (height[I],left_max[i-1]) Traversing from right to left, updating the right maximum each time, the right maximum of the current element is only related to the right maximum of the current element and one element on the right, namely :right_max[I] = Max (height[I],right_max[I + 1]); This method has two details: 1, consider the input array null, 2, initialize the first element of the left and right maxima array and the starting point of the traversal
Obviously, the time is order n. It’s traversed the array three times.
class Solution {
public:
int trap(vector<int>& height)
{
if(height.empty()) return 0;
int ans = 0;
int n = height.size(a);vector<int> left_max(n);
vector<int> right_max(n);
/ / initialization
// There is no element to the left of the first element, so the left maximum is itself
left_max[0] = height[0];
// There is no element to the right of the last element, so the right maximum is itself
right_max[n - 1] = height[n - 1];
The left maximum of the current element is related only to the left maximum of the current element and the left element
for(int i = 1; i < n; i++)
left_max[i] = max(height[i],left_max[i - 1]);
The right maximum of the current element is related only to the right maximum of the current element and one element on the right
for(int i = n - 2; i >= 0; i--)
right_max[i] = max(height[i],right_max[i + 1]);
for(int i = 0; i < n; i++)
{
ans += min(left_max[i],right_max[i]) -height[i];
}
returnans; }};Copy the codeDouble pointer method
Dynamic programming is traversed twice, using double Pointers to achieve only traversed once to achieve the left and right maximum array. Feel a very good explanation explanation: leetcode-cn.com/problems/tr…
1. Clarify the meaning of variables
Left_max: the maximum value on the left, which is found by traversing from left to right right_max: the maximum value on the right, which is found by traversing from right to left left: the current index processed from left to right right: the current index processed from right to left
2. Clearly known theorems:
Theorem 1: At some point I, the amount of water it can hold depends on the smaller of the maximum values on its left and right sides. Theorem 2: When we process the left subscript from left to right, left_max is trusted for it, but right_max is not trusted for it. Theorem 3: When we process from right to left to the right subscript, the maximum right_max on the right is trusted, but left_max is not.
3. Get the details
For position left, the maximum value on its left side must be left_max, and the maximum value on its right side must be “greater than or equal to” right_max. In this case, if left_max<right_max, then it knows how much water it can store. Whether or not a larger right_max appears on the right side in the future doesn’t matter. So when left_max is less than right_max, we want to deal with the left subscript, and vice versa.
4. Knowing this, you can write code:
class Solution {
public:
int trap(vector<int>& height)
{
if(height.empty()) return 0;
int ans = 0;
int n = height.size(a);int left = 0,right = n - 1;
int left_max = height[left], right_max = height[right];
while(left <= right)
{
if(left_max < right_max)
{
// If the current value is large, no need to accumulate.
if(left_max < height[left]) left_max = height[left];
else ans += (left_max - height[left]);
left++;
}
else
{
// If the current value is large, no need to accumulate.
if(right_max < height[right]) right_max = height[right];
elseans += (right_max - height[right]); right--; }}returnans; }};Copy the codeMonotonous stack
Although I have written the topic of monotonic stack close to 8 questions before, the idea of using monotonic stack in this question is not very clear. And cursory reading of the official solution did not understand the details.
The following two monotone stacks are better described:
The graph I use below is also from these two places piao.
Leetcode-cn.com/problems/tr…
Leetcode-cn.com/problems/tr…
The drab stack counts rain by row:
There are two other things to note:
1. We build a monotonically decreasing stack,Once the height of the added column is found to be greater than that of the stack header element, the stack header element is the column at the bottom of the groove, the second stack header element is the column to the left of the groove, and the added element is the column to the right of the groove.
As shown below:
2, encounter the same height of the column how to do.
When the same element is encountered, updating the subscript in the stack means that the element in the stack (the old subscript) is popped out and the new element (the new subscript) is added to the stack.
Because when we ask for width, if we meet columns of the same height, we need to use the right-most column to calculate width.
Now you can use the template to write code
This is a reference to the redundant code in code randomization to better understand the specific handling of three cases in the for loop.
class Solution {
public:
int trap(vector<int>& height)
{
if(height.empty()) return 0;
int ans = 0;
int n =height.size(a); vector<int> st;
for(int i = 0; i < n; i++)
{
// If the stack is empty, or the top element is greater than height[I], the stack is pushed
if( st.empty() || height[i] < height[st.back()])
{
st.emplace_back(i);
}
// If the stack is not empty and the top element ==height[I], update the top element to the right
else if(! st.empty() && height[i] == height[st.back()])
{
st.pop_back(a); st.emplace_back(i);
}
// If the stack is not empty and the top element is less than height[I]
else
{
while(! st.empty() && height[i] > height[st.back()])
{
int mid = st.back(a); st.pop_back(a);if(! st.empty())
{
int H = min(height[st.back()],height[i]) - height[mid];
int W = i - st.back(a)- 1; // The width between I and st.back()
ans += H * W;
}
}
st.emplace_back(i); }}returnans; }};Copy the code