This is the 11th day of my participation in the August More Text Challenge

Preface

Following the description of monotone stack, today we will talk about how to use the monotone stack template I gave you.

A monotone stack is a stack of elements that are monotone, often used to solve the problem of the next larger element.

Medium and Hard. I’m sure you’ll get something out of it.

  • 739. Daily temperature – force button

  • 42. Catch rainwater – force buckle

  • 84. The largest rectangle in the bar chart – force buckle

 // Monotonic stack template, if you do not understand can read my previous article
 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

739. Daily temperature

Description

Simulation

Let’s start with a table to see where the sample data came from

Day 1 The second day The third day The fourth day The fifth day On the sixth day 7 days The eighth day
The temperature 73 74 75 71 69 72 76 73
Next higher temperature The second day The third day 7 days On the sixth day On the sixth day 7 days There is no There is no
Number of days difference 1 1 4 2 1 1 0 0

The first thing that comes to mind, of course, is the violent solution. The two-layer for loop is iterated one by one, calculating the difference of days. The time complexity is O(n^2).

It is also very important to get the violent solution, after all, it is not always possible to think of the optimal solution, and we can also carry out the next optimization based on the violent solution.

To calculate the difference in the number of days between the next higher temperature, you need to find the first element to your right that is larger than you and calculate the difference of the subscripts.

It is obvious to use a monotone decrement (smallest stack header element) stack, and by the time complexity of O(n), you can find the first element to the right of each element that is larger than it, essentially substituting space for time.

  1. Why is it minus monotone?

    Answer: Because only when decrement, we can get the day difference, for example, when 74 is added to the stack, 73 can be removed from the stack, the first day of the day difference is obtained.

  2. How do you calculate the difference in days?

    A: Monotone stack only stores the subscripts of elements, and use t[I] directly for numerical comparison.

  3. How to use a template? ⏬

Now that we have analyzed to use monotone stack, we can directly put the three plate axe (template) out:

 / / template
 stack<int> stk;
 for (int i = 0; i < t.size(a); i++) {// Iterate over the temperature array t
     while(! stk.empty() && t[i] > t[stk.top()]) {   // Unstack condition, keep monotonic subtraction
         stk.pop(a); } stk.push(i);                                    // add subscripts to the stack
 }
Copy the code

Simulate the process of entering and exiting the stack in your mind:

  • The stack is empty, the subscript 0 of 73 is pushed, and the element in the stack is 0

  • 74 > 73,73 off the stack 74 on the stack, the difference of days is 1, element 1 in the stack

  • 75 > 74 74 off the stack 75 on the stack, day difference is 1, element in the stack 2

As can be seen from step 2, we need to calculate the difference of days by subscripting the elements in the stack before they exit the stack, and add a line:

     while(! stk.empty() && t[i] > t[stk.top()]) {   // Unstack condition, keep monotonic subtraction
         res[stk.top()] = i - stk.top(a);// Add the calculation
         
         stk.pop(a); }Copy the code

Solution

The complete code is as follows, you can try, the original link:

 // hrh 8/28 
 class Solution {
 public:
     vector<int> dailyTemperatures(vector<int>& t) {
         vector<int> res(t.size());
         stack<int> stk;     
 ​
         for (int i = 0; i < t.size(a); i++) {/ / traverse
             while(! stk.empty() && t[i] > t[stk.top()]) {   // Unstack condition
                 res[stk.top()] = i - stk.top(a);// Calculate the difference of days
                 stk.pop(a);// Keep monotone subtracting
             }
             stk.push(i);                                    / / into the stack
         }
 ​
         returnres; }};Copy the code

Conclusion

To summarize the analysis of monotone stack:

  1. 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 the monotone stack first. Its scope of application can be said to be very narrow, but the disadvantage is also a advantage, the type of question is very easy to identify.

  2. Analysis should be the first analysis of monotone, determine monotone reduction or monotone increase, directly write the template.

  3. On the basis of the template to delete, calculate the requirements of the topic.

Writing is not easy, ask a praise 💗💗

The remaining two questions will be updated in two days. If you are interested, you can click “follow” to communicate with each other

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