一.单调栈
定义：
单调栈是一种特殊的数据结构，本质上是栈，不过在栈的基础上，要求栈内元素保持单调性（单调递增或单调递减）
原理
单调栈在入栈操作时，会根据栈内元素的单调性要求对入栈元素进行处理。当新元素入栈时，如果加入该元素会破坏栈的单调性，就先将栈顶元素出栈，直到加入新元素后栈依然满足单调性，再将新元素入栈。
单调递增栈
栈内元素从栈底到栈顶是单调递增的。当有新元素入栈时，如果新元素小于栈顶元素，则将栈顶元素出栈，直到新元素大于等于栈顶元素，再将新元素入栈。
单调递减栈
栈内元素从栈底到栈顶是单调递减的。当有新元素入栈时，如果新元素大于栈顶元素，则将栈顶元素出栈，直到新元素小于等于栈顶元素，再将新元素入栈。
应用场景：
1. 求下一个更大元素
给定一个数组，对于每个元素，找到它右边第一个比它大的元素。
2. 求每日温度问题
给定一个数组表示每天的温度，对于每一天，计算需要等待多少天才能等到一个更暖和的温度。
3. 求柱状图中最大矩形面积
在一个由柱子组成的柱状图中，计算能够形成的最大矩形面积。
这是单调栈的一道非常非常基础的母题，解决这内题我们最先想到的肯定是暴力解法，但实践过后发现时间复杂度太高了直接就T掉了。那么我们必须进行优化，这就要用到单调栈来降低时间复杂度了。由于每个元素最多入栈和出栈一次，因此时间复杂度为O(n)，n是数组的长度。代码如下：
//暴力解法
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <string>
#include <cstdio>
#include<cmath>
#include<stdio.h>using namespace std;void f(vector<int>& a,int n)
{for (int i = 1; i <= n; i++){int b = a[i];int t = 1;int s;for (int j = i + 1; j <= n; j++){if (a[j] > b){t = 0;s = j;break;}}if (t == 0){printf("%d ", s);}else{printf("0 ");}}printf("\n");
}int main()
{int n;cin >> n;vector <int> a(n + 1);for (int i = 1; i <= n; i++){cin >> a[i];}f(a, n);return 0;
}//单调栈解法
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <string>
#include <cstdio>
#include<cmath>
#include<stdio.h>using namespace std;
#define max 3000005
void f(vector<int> &a, int n)
{vector<int> ret(n + 1, 0);vector<int> stack(n + 1);int top = -1;for (int i = 1; i <= n; i++){while (top != -1 && a[i] > a[stack[top]]){ret[stack[top]] = i;top--;}top++;stack[top] = i;}for (int i = 1; i <= n; i++){printf("%d ", ret[i]);}cout << endl;
}int main()
{int n;cin >> n;vector<int>a(n + 1);for (int i = 1; i <= n; i++){cin >> a[i];}f(a, n);return 0;
}二.单调队列
定义：
单调队列本质上是一个队列，不过队列中的元素保持单调递增或单调递减的顺序。与单调栈不同的是，单调队列可以在队首和队尾进行操作，这使得它能够处理滑动窗口这类需要动态维护区间信息的问题。
原理
单调队列的核心原理是在元素入队和出队的过程中，通过一定的规则保证队列中元素的单调性。当有新元素加入队列时，会从队尾开始移除那些破坏单调性的元素，然后将新元素插入到合适的位置，以维持队列的单调性。同时，根据滑动窗口的移动，会从队首移除那些已经不在当前窗口范围内的元素。
操作
入队操作
当有新元素要加入单调队列时，从队尾开始检查，如果队尾元素不满足单调性要求（对于单调递增队列，队尾元素大于新元素；对于单调递减队列，队尾元素小于新元素），则将队尾元素出队，直到满足单调性要求后，将新元素加入队尾。
出队操作
根据滑动窗口的移动，当队首元素不在当前窗口范围内时，将队首元素出队。
应用场景
1. 滑动窗口最大值问题
给定一个数组和一个固定大小的滑动窗口，要求在滑动窗口从数组的一端移动到另一端的过程中，找出每个窗口内的最大值。
2. 优化动态规划问题
在一些动态规划问题中，需要在一个区间内寻找最值来更新状态，使用单调队列可以将时间复杂度从 O(n^2) 优化到 O(n)。
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <string>
#include <cstdio>
#include<cmath>
#include<algorithm>using namespace std;int n, k;
int a[1000005],e1[1000005],e2[1000005];void min()
{int head = 1, tail = 0;for(int i=1;i<=n;i++){while (head <= tail && e1[head] < i - k + 1) head++;while (head <= tail && a[i] < a[e1[tail]]) tail--;e1[++tail] = i;if (i >= k){cout << a[e1[head]]<<' ';}}cout << endl;
}void max()
{int head = 1, tail = 0;for (int i = 1; i <= n; i++){while (head <= tail && e2[head] < i - k + 1) head++;while (head <= tail && a[i] > a[e2[tail]]) tail--;e2[++tail] = i;if (i >= k){cout << a[e2[head]]<<' ';}}cout << endl;
}
int main()
{cin >> n >> k;for (int i = 1; i <= n; i++){cin >> a[i];}min();max();return 0;
}
