Preface

          Conduct Monotone stack and monotone queue ！

One 、 Monotonic stack

brief introduction

When the current face cannot extend to the back （ There is no possibility of a new answer ）, The front is useless as redundancy , You can calculate the answer separately and then remove

The template questions

LeetCode 84. The largest rectangle in the histogram

LeetCode 84. The largest rectangle in the histogram Original link

Ideas ：

$(1)$ Double pointer cannot be used for this question , The condition for deciding whether to use double pointers is that the title is related to the two ends . This question is not only related to the two points, but also related to the middle content （ It is related to the height of each in the interval , Who has the least influence on the final result answer ）;

$(2)$ Maintain a rectangle with increasing height ;

$(3)$ Only at the end of the modification （ Insert and delete ） With the stack ;

Code analysis ：

class Solution {
    
public:
    int largestRectangleArea(vector<int>& heights) {
    
        heights.push_back(0);  //  Add a after the original array 0（ Cumulative width *0=0  useless ）, This avoids the fact that the given data is incremental , Finally, all elements in the stack can be ejected （ After calculating the answer every time ）,0 It can help move every element while Loop to calculate and pop up . At last, help empty the stack 
        stack<Rec> stk;  //  Rectangles are stored in the stack , The height and width of the rectangle may be different （ Because you can merge multiple rectangles ）
        int ans = 0;

        for (int h : heights) {
      //  Consider each height 
            int accumulated_width = 0;  //  Take the current as the right boundary (0) Calculate the cumulative width , So every time 0,
            //  Be careful ： Before accessing any data structure , First judge whether it will cross the boundary , Keep playing , Maybe the stack is empty , To determine whether the stack is empty , Only when it is not empty can there be a stack top , So the visit stk It is necessary to judge whether it is empty 
            while (!stk.empty()  && stk.top().height >= h) {
      //  To the top of the stack （ the previous ） Higher than the current height , The top of the stack cannot extend to the right , You can compare and calculate the answers （ Previous ）（ You need to calculate the previous answers one by one to the right and update ）
                accumulated_width += stk.top().width;  //  Accumulate one width at a time 
                ans = max(ans, accumulated_width * stk.top().height);
                stk.pop();  //  Out of the stack , Stop until the increment is satisfied ,
            } 
            stk.push({
    h, accumulated_width + 1});  //  If the data given is 1,2,3  The given data is incremental , Not through while loop 
        }
        return ans;
    }

private: 
    struct Rec {
    
        int height;
        int width;
    };
};

• Time complexity ： Total number of runs , The total number of times is push and pop The number of , Each rectangle can be put on and out of the stack at most once ,2n = O(n) Time complexity of

Two 、 A monotonous queue

brief introduction

1. Conditions for using double pointers ： The information maintained is one point , for example , Water connection problem （ And the only i、j The values of the two endpoints are related ）, Sum of two numbers （ The sum of the values of the two endpoints equals target）.
2. If the maintained information is an interval, consider using prefix sum and monotone queue
   • Use prefix and ： Satisfy the property of interval subtraction , refer to [l, r] Information can be provided by [1, r] And [1, l-1] Information export . for example , Section l~r The sum of can be determined by Section 1~r Sum of minus interval 1~l-1 And get .
   • With monotonic queues

The template questions

LeetCode 239. Maximum sliding window

LeetCode 239. Maximum sliding window Original link

Ideas ：

$(1)$ When the window moves from front to back, you need to pay attention to two messages , One is time （expire_time）, The other is the value size ;

$(2)$ for example ,[-1, -3, 5],expire_time(-1) < expire_time(-3) < expire_time(-5), Value size ,-1 < -3 < 5;

$(3)$ Find the maximum value of the window in terms of time ,expire_time The later it is, the longer it lives, the better , In terms of value, the larger the value, the better . that -1 and -3 be relative to 5 Just say , It's redundant ,5 If you are -1 and -3 It must not be the answer .

$(4)$ redundancy ： One subscript is i, The other subscript is j, If i < j, be i Out of bounds first , meanwhile nums[i] <= nums[j] be i It's redundancy . No redundant ：[3, -1, -3],expire_time(3) < expire_time(-1) < expire_time(-3), 3 > -1 > -3, What is maintained is a decreasing sequence .

Code analysis ：

class Solution {
    
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    
        vector<int> ans;
        //  deque , Save subscript , Subscript indicates time attribute 
        deque<int> q;

        for (int i = 0; i < nums.size(); i ++) {
    
             //  Ensure that the team leader is legal . Only when there are elements in the queue can they be ejected , First ensure that the queue is not empty ,i-k  Is the position out of bounds , Than  i-k  I was out of bounds when I was young ,
            while (!q.empty() && q.front() <= i - k) q.pop_front(); 
            //  Maintain queue monotonicity , Insert new elements 
            while (!q.empty() && nums[q.back()] <= nums[i]) q.pop_back();  
            q.push_back(i);
            //  Take the team leader as the optimal decision , Window from  k-1  Start counting 
            if (i >= k - 1) ans.push_back(nums[q.front()]);
        }
        return ans;
    }
};

summary ：

1. Features of sliding window topics ： There are two attribute sequences , One is time , The other is the attribute given by the title （ This question is about size ）.

2. Consider whether to maintain monotonically decreasing series or monotonically increasing series. From the fixed time attribute

   • Time subscript ： Two subscripts j1 and j2 Who was earlier ,j1 < j2, First set the time as less than
   • Then write about the value j1 Than j2 Excellent conditions , This problem is to find the maximum , therefore nums[j1] > nums[j2] yes j1 Than j2 Excellent conditions
   • If the condition is > What we maintain is a decreasing sequence , yes < The maintenance is incremental sequence

3. If the decreasing sequence is maintained, the header is optimal , Take the header of the current window max As the answer , Be careful , When accessing any data structure, we must judge whether it is legal , When taking the answer, you must first judge whether the answer is legal （ The answer may be out of date , If it expires, remove it ）

4. Make a question step template

   • for Every element
     (1) Judge the legitimacy of the answer ：while ( The head of the team is overdue ) Team leader out of team
     (2) Taking the head of the team is the best option , Calculation answer
     (3) Maintain monotonicity ：while ( The tail of the team and new elements are not monotonous ) A party out of the team , Put a new element at the end of the team

(2) and (3) The order of is variable , It depends on this i Is it desirable , This question is to find i For the end of the window Max,i Maybe the answer is ,i Take , contain i, At this time, we should do (3), new i Put it in and take the head of the team . Some topics i It may be calculated by the number in front of it ,i Not an option , At this time, we should do (2), Take the head of the team first and then calculate i, Then insert it into the queue .