前言

          进行 单调栈与单调队列 ！

一、单调栈

简介

当前面不能延伸到后面时（没有作为新的答案的可能性），前面作为冗余就没用了，可以先单独计算答案然后去掉

模板题

LeetCode 84. 柱状图中最大的矩形

LeetCode 84. 柱状图中最大的矩形 原题链接

思路：

$(1)$ 此题不能用双指针，决定能否用双指针的条件是题目跟两端点有关。此题不仅与两端点有关还与中间内容有关（与区间内的每一个的高度都有关，谁最小影响最终的结果答案）；

$(2)$ 维护的是一个高度递增的矩形；

$(3)$只有在末尾发生修改（插入和删除）用栈；

代码剖析：

class Solution {
    
public:
    int largestRectangleArea(vector<int>& heights) {
    
        heights.push_back(0);  // 在原数组后面补一个0（累加宽度*0=0 没用），这样就避免了给的数据是递增的，最后这样可以将栈中所有元素弹出（每次计算完答案后），0可以帮助将每个元素走while循环进行计算和弹出。在最后帮助将栈清空
        stack<Rec> stk;  // 栈中存的是矩形，矩形的高度和宽度可能不一样（因为可以将多个矩形合并）
        int ans = 0;

        for (int h : heights) {
      // 考虑每一种高度
            int accumulated_width = 0;  // 以当前为右边界(0)进行累加宽度计算，所以每次都是0，
            // 注意：访问任何数据结构之前，先判断是否会越界，一直弹，可能弹到栈为空，要判断栈是否为空，只有不为空才有栈顶，所以访问stk前要判断是否为空
            while (!stk.empty()  && stk.top().height >= h) {
      // 栈顶（上一个）比当前高度高，栈顶的就无法向右延伸，可以进行答案比较计算（之前的）（需要向右挨个计算之前的答案并更新）
                accumulated_width += stk.top().width;  // 每次累加一个宽度
                ans = max(ans, accumulated_width * stk.top().height);
                stk.pop();  // 出栈，直到满足递增的时候停止，
            } 
            stk.push({
    h, accumulated_width + 1});  // 如果给的数据是1,2,3 给的数据是递增的，没有经过while循环
        }
        return ans;
    }

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

• 时间复杂度：总的运行次数，总的次数为 push 和 pop 的数量，每个矩形至多入栈和出栈各一次，2n = O(n) 的时间复杂度

二、单调队列

简介

1. 使用双指针的条件：维护的信息是一个点的，例如，接水问题（只和 i、j 两个端点的值有关），两数之和（两个端点的值相加等于 target）。
2. 如果维护的信息是一段区间的话考虑用前缀和与单调队列
   • 用前缀和：满足区间减法性质，指的是 [l, r] 的信息可以由 [1, r] 与 [1, l-1] 的信息导出。例如，区间 l~r 的和可以由 区间 1~r 的和减去区间 1~l-1 的和得到。
   • 用单调队列

模板题

LeetCode 239. 滑动窗口最大值

LeetCode 239. 滑动窗口最大值 原题链接

思路：

$(1)$ 窗口从前往后移动时需要关注两个信息，一个是时间（expire_time），另一个是值大小；

$(2)$ 例如，[-1, -3, 5]，expire_time(-1) < expire_time(-3) < expire_time(-5)，值大小，-1 < -3 < 5；

$(3)$ 求窗口最大值从时间上来看，expire_time 越晚表明存活的时间越长则越好，从值来看值越大越好。那么 -1 和 -3 相对于 5 来说就用了，就是冗余的，5 在的话 -1 和 -3 一定不能是答案。

$(4)$ 冗余：一个下标为 i，另一个下标为 j，如果 i < j，则 i 先出界，同时 nums[i] <= nums[j] 则 i 是冗余。不冗余：[3, -1, -3]，expire_time(3) < expire_time(-1) < expire_time(-3)， 3 > -1 > -3，维护的是一个递减的序列。

代码剖析：

class Solution {
    
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    
        vector<int> ans;
        // 双端队列，存下标，下标表示时间属性
        deque<int> q;

        for (int i = 0; i < nums.size(); i ++) {
    
             // 保证队头合法。队列中有元素才能弹出，先保证队列不为空，i-k 是出界的位置，比 i-k 小就出界了，
            while (!q.empty() && q.front() <= i - k) q.pop_front(); 
            // 维护队列单调性，插入新元素
            while (!q.empty() && nums[q.back()] <= nums[i]) q.pop_back();  
            q.push_back(i);
            // 取队头为最优决策，窗口从 k-1 开始算
            if (i >= k - 1) ans.push_back(nums[q.front()]);
        }
        return ans;
    }
};

总结：

1. 滑动窗口的题目的特点：有两个属性顺序，一个是时间，另一个是题目给的属性（本题是比大小）。

2. 考虑的是维护的是单调递减的系列还是单调递增的序列通过固定时间属性来看

   • 时间下标：两个下标 j1 和 j2 谁更早，j1 < j2，先将时间定为小于号
   • 再写出关于值 j1 比 j2 优的条件，本题是求最大值 ，所以 nums[j1] > nums[j2] 是 j1 比 j2 优的条件
   • 如果条件是 > 维护的就是递减序列，是 < 维护的就是递增序列

3. 维护的是递减序列则头部是最优，取队头为当前窗口的 max 作为答案，注意，访问任意一种数据结构时都要判断其是否合法，取答案时一定要先判断答案是否合法（这个答案可能出界即过期了，如果过期就去掉）

4. 做题步模板

   • for 每个元素
     (1) 判断答案合法性：while (队头过期) 队头出队
     (2) 取队头为最佳选项，计算答案
     (3) 维护单调性：while (队尾与新元素不满足单调性) 队尾出队，在队尾放入一个新元素

(2) 和 (3) 的顺序可变，取决于这个 i 是否可取，本题是求以 i 为结尾的窗口的 Max，i 可能是答案，i 可取，包含 i，这时应该先做 (3)，新的 i 放进去再取队头。有的题目 i 可能是通过其前面的数算出来的，i 不可取，这时应该先做 (2)，先取队头然后算 i，再将其插入队列。