Algorithm Of DS——Monotonic Stack & Queue

Before：最近在de STLite的最后一个数据结构map。周二用一个下午+一个晚上搓完后，开始了《漫长》的debug环节，目前来看问题出在erase上（AVL倒也合理），RE麻了…😰😰😰遂开始了算法学习呜呜呜。立个小目标，这周结束前把map过了吧求求了😢😢😢最近还是很开心的，也很轻松，希望能轻松一学期（bushi🤣🤣🤣）今天知道了一件事，让我觉得人间值得😣😉☺️

Algorithm of Data Structure 1 单调栈&单调队列&栈模拟递归

单调栈

定义：栈内元素满足某种单调性质，可以单增也可以单减

在处理每个元素时，将其与栈顶元素进行比较，如果当前元素大于（或小于）栈顶元素，则将栈顶元素出栈，直到满足单调性质为止。然后，将当前元素入栈，继续处理下一个元素（当前元素必须入栈）

单调栈可以快速找到每个元素的下一个更大（或更小）元素，时间复杂度为O(n)（n为序列的长度）

具体来说，单调递增栈可用于寻找下一个更小元素，而单调递减栈可用于寻找下一个更大元素，并且只需要遍历整个序列一次

Example：找到数列中每个元素下一个比它大的元素下标（1 — base）

int top = 0; //栈顶位置
stack[top] = 0; //a[0]入栈  stack数组记录栈内元素下标
for(int i = 1;i < n;i ++){
    while(top >= 0 && a[stack[top]] < a[i]){
        ans[stack[top]] = i + 1; //记录答案
        top --; //当前栈顶元素出栈
    }
    stack[++ top] = i;
}
while(top >=0){
    ans[stack[top --]] = 0; //栈内剩余元素不存在下一个比它大的元素
}

总结：需要一个stack数组记录栈内情况，一个top记录栈顶位置，一个a存储原本序列数据，和一个ans存储答案

单调栈例题

luogu P1901

• 某地有N个能量发射站排成一行，每个发射站i都有不相同的高度Hi，并能向两边（两端的发射站只能向一边）同时发射能量值为Vi的能量，发出的能量只被两边最近的且比它高的发射站接收。

• 显然，每个发射站发出的能量有可能被0~2个其他发射站所接受。

• 请计算出接收最多能量的发射站接收的能量是多少。

小黄题，15分钟速通😋 Strong女也只能切黄题了呜呜呜

#include<bits/stdc++.h>
using namespace std;
int h1[1000005];
int h2[1000005];
int stack1[1000005];
int stack2[1000005];
int v1[1000005];
int v2[1000005];
int ans1[1000005];
int ans2[1000005];
int total1[1000005];
int total2[1000005];
int main() {
    int n;
    cin >> n;
    for(int i = 0;i < n;i ++) {
        cin >> h1[i];
        cin >> v1[i];
    }
    for(int i = 0;i < n;i ++) {
        h2[i] = h1[n - 1 -i];
        v2[i] = v1[n - 1- i];
    }
    int top1 = 0;
    int top2 = 0;
    stack1[top1] = 0;
    for(int i = 1;i < n;i ++) {
        while(top1 >= 0 && h1[stack1[top1]] < h1[i]) {
            ans1[stack1[top1]] = i;
            total1[i] += v1[stack1[top1]];
            top1 --;
        }
        stack1[++ top1] = i;
    }
    while(top1 >= 0) {
        ans1[stack1[top1 --]] = -1;
    }

    stack2[top2] = 0;
    for(int i = 1;i < n;i ++) {
        while(top2 >= 0 && h2[stack2[top2]] < h2[i]) {
            ans2[stack2[top2]] = i;
            total2[i] += v2[stack2[top2]];
            top2 --;
        }
        stack2[++ top2] = i;
    }
    while(top2 >= 0) {
        ans2[stack2[top2 --]] = -1;
    }

    int maxE = 0;
    for(int i = 0;i < n;i ++) {
        int current = total1[i] + total2[n - 1 - i];
        if(current > maxE) {
            maxE = current;
        }
    }
    cout << maxE;
}

单调队列

高效地维护队列中元素的单调性（递增或递减），同时支持在队列两端的插入和删除操作

• 可在队首出队

• 仅在队尾入队

• 如果影响单调性，可能从队尾出队

省流：其实是一个双端队列（deque）（这不是隔壁这次大作业嘛🤣有福了）

它通常用于解决需要在一个滑动窗口（或固定长度的子数组）内找到最大值或最小值的问题

• 插入元素：当新元素进入窗口时，从队列尾部移除所有小于新元素的元素，然后将新元素插入队列尾部。

• 移除元素：当元素离开窗口时，如果它是队列头部的元素，则从队列头部移除。

• 获取最值：队列头部的元素始终是当前窗口的最大值（或最小值，取决于单调性）

可实现在O(1)的时间复杂度下获得最值比如我们现在要一个递增的单调队列

int minFront = 0;
int minBack = 0;
for(int i = 1;i < n;i ++){
    num[i] = read();
    while(minBack >= minFront && minWin[minFront] <= i - k){ //队头指针小于等于队尾指针 && 队头元素索引已经不在窗口范围内
        ++ minFront;
    }
    while(minBack >= minFront && num[i] < minWin[minBack]){
        -- minBack; // 将破坏单调性的元素出列
    }
    //加入队列
    minWin[++ minBack] = num[i];
    if(i >= k){
        cout << minWin[minFront];
    }
}

单调队列例子

小Z的家门口种了N棵树，第i棵树在目标点xi，高度hi。如果一棵树左边D距离内和右边D距离内有高度至少是它的两倍的树，那么小Z认为这棵树不够茁壮。春天到了，他想给不够茁壮的树多施点肥，请你帮忙数数有几棵不够茁壮的树。

思路：长度为D（若不足D 也可）的数组（窗口），移动即可。两个方向都扫一遍

栈模拟递归

递归过程：

1. 执行代码块0

2. 保存现场准备进入下一层

3. 接受下层返回的数据

4. 恢复现场

5. 继续执行代码块1

直接用递归程序实现递归时，第二步和第四步都是编译器在帮助你完成而非递归实现，我们期望：自己用实现保存现场和恢复现场

用栈模拟递归的优势在于：

1. 避免递归深度限制

2. 更直观的控制流程

3. 避免递归调用的开销

END

你可以当我哑巴一样你不会看见我的抵抗请别怕我受伤 我自己会圆场