全文目录
单调栈，顾名思义就是具有单调性的栈。通常是用来求数组中的左边第一个比自身小或者大的数，使用场景还是比较有限的。但是对于解题还是有着很大的帮助的。
我们还是通过题目来进行讲解。
对于这种题目，首先想到的都是暴力求解：
枚举每一个位置，然后从这个位置的前一个位置元素遍历，找到第一个小于它的元素的位置就是我们所求的。
那么这时的时间复杂度就会是 O(n^2) 效率很低。
思路优化：
我们可以发现这不就是我们从前往后枚举，然后从后往前遍历么 —— 这就符合了栈的先进后出。那么就可以在从后往前遍历的时候构建一个单调栈，将大于它的数都出栈，那么这个栈就是一个单调递增的单调栈。
如果当前位置有解,这么这个解一定是栈顶的元素 —— 因为大于它的我们都弹栈了， 然后当前元素又入栈，我们发现，栈里面栈顶元素的解一定是栈顶元素下面的那个元素。
利用这个性质,我们比较时就可以跳过许多不需要比较的位置了。
比如我们现在要入栈的是 8， 然后栈顶元素是 7， 那么答案一定是 7， 因为 7 一定是最后入栈的。如果栈顶元素是 9，那么 9 弹出，此时栈顶是 6， 那么答案就是 6， 因为 6 一定是距离 9 最近的并且小于它的元素。其他位置的元素要么大于 9， 要么距离远，都不符合条件。
#include <iostream>
using namespace std;
const int N = 100010;
int a[N], n, tt;
int main()
{
tt = -1;
cin >> n;
for (int i = 0; i < n; i++)
{
int x;
cin >> x;
while (tt > -1 && a[tt] >= x) tt--; // 将栈顶大于a[i]的数出栈，保持单调性
if (tt == -1) cout << -1 << ' ';
else cout << a[tt] << ' ';
a[++tt] = x;
}
return 0;
}
暴力求解：
我们还是先来看一下使用暴力求解的做法：
枚举每个区间，然后在区间中寻找最大值和最小值。
这时的时间复杂度就是 O(n * k) 效率还是比较低的。
思路优化（最小值为例）：
我们可以根据暴力求解的规律发现，每个元素都是先进先出的 —— 满足队列的性质，那么我们就可以通过队列来维护每一个区间。
如果队列中存在两个元素，满足
a[i] >= a[j]且i < j，那么无论在什么时候我们都不会取a[i]作为最小值了（因为j比i活得久），所以可以直接将a[i]删掉。
此时队列中剩下的元素严格单调递增，所以队头就是整个队列中的最小值，可以用 O(1) 的时间找到。
为了维护队列的这个性质，我们在往队尾插入元素之前，先将队尾大于等于当前数的元素全部弹出即可。
这样所有数均只进队一次，出队一次，所以时间复杂度是 O(n) 的。
#include <iostream>
using namespace std;
const int N = 1e6 + 10;
int a[N], q[N]; // q只是用来维护a的队列，存放的是下标
int head, tail = -1;
int n, k;
int main()
{
cin >> n >> k;
for (int i = 0; i < n; i++)
cin >> a[i];
// 寻找最小值
// 先移动左端点，后移动右端点
for (int i = 0; i < n; i++)
{
// 因为确定了每次只往后移动一位，所以用if
// 当队列中有元素，并且队头的元素小于区间的左端点的时候右移
if (tail >= head && i - k + 1 > q[head]) head++;
// 找最小值，需要使用递增队列
// 通过观察到的规律进行单调性的维护
while (tail >= head && a[q[tail]] >= a[i]) tail--;
q[++tail] = i;
if (i >= k - 1) cout << a[q[head]] << ' '; // 控制区间输出
}
puts("");
head = 0, tail = -1;
for (int i = 0; i < n; i++)
{
if (tail >= head && i - k + 1 > q[head]) head ++;
while (tail >= head && a[q[tail]] <= a[i]) tail --; // 只需要改变队列的递增性质
q[++tail] = i;
if (i >= k - 1) cout << a[q[head]] << ' ';
}
return 0;
}