一、单调栈

1、简要解释

顾名思义，单调栈就是整个栈中的元素大小从栈底到栈顶依次增大或减小，这种栈称之为单调栈。

而栈这个数据结构满足一个特性就是，数据先进后出，后进先出。如果这个栈从栈底到栈顶依次增大，那么栈顶元素一定是当前栈中最大的。

下面我们来以题带点，简要说一下单调栈的用处。

2、题目练习

 题目来源：acwing 单调栈习题

Acwing 单调栈https://www.acwing.com/problem/content/832/

 这里我把题目截图放出来，方便大家观看。

 3、解题思路

突破点：左边第一个比它小的数据

我们遍历数组的时候，肯定是从左到右依次列入数组当中，然后找比他小的值，普通方法肯定是遍历数组并遍历下标，找到离他最近的并且比它小的数据，但这样做时间复杂度很高，因此我们希望优化一下。

既然是第一个，结合每一次遍历这些数据都会把它一一存放到数组中，因此我们想到了先进后出的栈数据结构，保证了后进的数据优先被遍历到。

随后，大家设想一下，如果该栈中，存在了后一个数据比前一个数据小的情况，那么既然要找比要进栈的数据小的，肯定优先是后面那个数据被优先选择，前一个大点的数据肯定没有机会。因此，我们维持一个单调递增的栈，下面我画个图给大家示意一下。

由于加入了2这个元素，比2小的数据肯定比3，4小，比3，4大的肯定比2大，而且2又是处于栈顶，是离要比较的数据最近的数据，3，4肯定没有机会，所以直接扔掉。

代码展示

# include <iostream>

using namespace std;

const int N = 100;
int n;
int arr[N];
int stk[N], top, bottom;

int main() {
    int flag = -1;
    scanf("%d", &n);
    for (int i = 0; i < n; i ++) scanf("%d", &arr[i]);
    
    for (int i = 0; i < n; i ++) {
        while (top != bottom && stk[top] >= arr[i]) top--;
        if (top == bottom) cout << flag << " ";
        else {
            cout << stk[top] << " ";
        }
        stk[++top] = arr[i];
    }    
}

二、单调队列

1、简要解释

单调队列和单调栈差不了太多，都是里面的数据呈现单调递增或单调递减。

队列这里和栈不同的是，栈是先进后出，队列是先进先出。

2、题目练习

Acwing 滑动窗口https://www.acwing.com/activity/content/problem/content/868/

3、解题思路

既然这道题要找最大最小值，我们就从最小值说起，最大值道理一样。

常规做法的话肯定是定义头指针和尾指针，先是移动三个数据进入一个数组，然后排序找到最小值，这样的时间复杂度肯定是kn，很大。

那么怎么优化呢？

我们不想通过排序方式去找，那么就简化成O（1），也就是直接找到，由于窗口是移动的，当有第四个数据进入窗口时，第一个数据会被踢出窗口，因此我们想到了先进先出的队列思想。

既然又要直接找到该最小值，完成O（1）复杂度，那么就直接操纵队头数据（队列有相关函数），也就是让最小值处于队头位置。

我们再想，窗口中，如果出现前一个数据比后一个数据大，那么直到这个大的数据出窗口的时候，小数据依旧在窗口内，排老小永远排不到大的，因此，我们设计一个思路就是：新加入的数据如果小于队尾元素数据，直接从队尾出队列，直到新加入的数据前面没有比它大的为止。同时，别忘了当窗口内数据比规定大小大的时候，队头元素要强制出队列。

文字太多了，求最小值核心代码出示如下：

int head = 0, tail = 0; // 定义头指针和尾指针
    // 最小值
    for (int i = 1 ; i <= n; i ++) {
        // 当队列中有数据并且队头元素已经存活了k次循环，强制出队列
        if (head < tail && q[head + 1] == i - k) head++;
        
        // 如果队列数据比要进入队列的数据大，则队列中数据从队尾撤出队列.
        while (head < tail && arr[q[tail]] > arr[i]) --tail;
        q[++tail] = i;
        if (i >= k) {
            cout << arr[q[head + 1]] << " ";
        }
    }

求最大值道理和最小值一样，在这里也出示一下代码：

int head = 0, tail = 0; // 定义头指针和尾指针
// 最大值
    for (int i = 1; i <= n; i ++) {
        if (head < tail && q[head + 1] == i - k) head++;
        while (head < tail && arr[q[tail]] < arr[i]) --tail;
        q[++tail] = i;
        if (i >= k) {
            cout << arr[q[head + 1]] << " ";
        }
    }