This is the 12th day of my participation in the August Challenge

Preface

The daily temperature is the same as the daily temperature.

Remember the steps from the previous part:

  1. Monotone stack: In general, if you are asked to find the first element to the left (right) of an element that is larger (smaller) than you are, you should think of monotone stacks first. It can be said that the scope of application is very narrow, but the disadvantage is also the advantage, this kind of question type is easy to identify.
  2. Monotone analysis: analysis should be the first analysis of monotone, judgment monotone reduction or monotone increase, directly give three plate axe (template).
  3. Calculation: on the basis of the template to delete, calculate the requirements of the topic.

Post the monotonic stack template as usual:

 // The monotonic stack template
 for(traversing the array) {whileThe stack is not empty && the top element of the stack is compared to the current array element. } into the stack; }Copy the code

42. After the rain

Description

Simulation

Ideas:

  1. Looking at the diagram, only when the next element greater than or equal to itself is inserted will the groove be formed to catch the rain water. So obviously, we should use the monotonic stack.
  2. How to judge monotonicity? Obviously, the smaller element can be inserted directly, and the larger element should be removed from the stack, so we need a decrement stack (with the smallest element at the top of the stack).
  3. How do you calculate the area? The base * height is known to everyone and is calculated row by row. The following is the analysis:

First of all, what should be stored in the monotonic stack, the height of each column? No, no, no! We need subscripts to calculate the width, and the subscripts can get directly to the height, so we only need a monotonic stack to store the subscripts.

A graph is drawn to simulate the calculation process. A set of numbers [2,1,0,3] are stacked from left to right:

  • 2 goes on the stack, empty, subscript I goes on the stack, element in the stacki 。
  • 1<2, it goes directly to the stack, the element in the stacki, i+1 。
  • 0<1, go directly to the stack, inside the stack elementi, i+1, i+2 。
  • 3>0, store 0 as the base and exit the stack, calculate the area of the groove: height is 1, select the smaller one between 3 and the current top element 1 (barrel theory, look at the short one); The base is 1, the subscript of 3 minus the subscript of 1(i+3) - (i+2); Total area +1, continue to judge 👇
  • 3>1, save 1 as the base and exit the stack, calculate the area of the groove: the height is 1, because 1 is the base, at this time the top element of the stack is 2, so the height is2-1 = 1, the subscript calculates the base to be 2; Total area +2, continue to judge 👇
  • If 3> 2,2 exits the stack, but the stack is empty. 3 finally gets pushed, and finally the element in the stacki+3.
  • The total area is 3

Read simulation process, believe you already had train of thought, drab the stack that reduces, 3 board axe whole, we need to calculate area when giving a stack only can. The full code is given below 🍉🍉🍉

Solution

 // hrh 8/29 
 class Solution {
 public:
     int trap(vector<int>& h) {
         stack<int> stk;    
         int res = 0;
         
         // It is the same.
         for (int i = 0; i < h.size(a); i++) {while(! stk.empty() && h[i] >= h[stk.top()]) {
                 int base = h[stk.top()];        // Save the base and unstack it
                 stk.pop(a);// Calculate the area if the stack is not empty
                 if(! stk.empty()) {             
                     int height = min(h[stk.top()], h[i]) - base;
                     int width = i - stk.top() - 1;
                     res += height*width;
                 }
             }
             
             stk.push(i);
         }
 ​
         returnres; }};Copy the code

Conclusion

Let’s review the process again:

  1. Determine if the problem can be solved using monotone stacks.
  2. Judge monotone, give three plate axe.
  3. Simulate the calculation process, delete the template to get the result.

It is Hard to solve the problem

We will continue to update the next question tomorrow. Thank you for watching 😄

I am Mancuoj, more interesting articles: Mancuoj personal homepage – article – Nuggets (juejin. Cn)