• 题外话
  2333感觉uups里面真的是愈发有趣、有趣得一塌糊涂不可收拾
  点击加入群聊【科技区UP主抱团交流群】
  欢迎入坑参与身♂心♂愉悦的聊天

单调栈

定义

单调递增或单调减的栈，只用到它的一端，利用它可以用来解决一些ACM/ICPC和OI的题目，如RQNOJ 的诺诺的队列等。

假设如下是一个栈内元素的排列情况(单调递增的栈)：
$1 \rightarrow 2 \rightarrow 4 \rightarrow6$
此时插入情况有两种：
(1)插入元素大于栈顶元素
当插入$7$时，因$7 > 6$，满足单调递增的条件，故可以直接加入栈
此时：
$1\rightarrow 2 \rightarrow 4 \rightarrow 6 \rightarrow 7$
(2)插入的元素小于栈顶元素
当插入$3$时，为了满足单调递增栈的性质，需要先将栈顶的$4,6$弹出，再插入
此时
$1\rightarrow 2\rightarrow 4$
$1 \rightarrow 2$
$1 \rightarrow 2\rightarrow 3$

功能

一言以蔽之
一个元素向左遍历的第一个比它小的数的位置就是将它插入单调栈时栈顶元素的值，若栈为空，则说明不存在这么一个数。然后将此元素的下标存入栈，就能类似迭代般地求解后面的元素

模板题

题目

【问题描述】

一个数列有N个整数，记为A1…An。
对于第i个数Ai，定义它的控制范围为由数列中不超过Ai的整数组成并且包含Ai的极大的区间[Li, Ri]。
对每个数求出它的控制范围。

【输入格式】

输入文件的第一行包括一个正整数N,表示有N个数。
第二行有N个整数，之间用空格隔开。

【输出格式】

输出文件包括N行，每行2个整数，依次表示每个整数的控制范围。

【样例输入】
3
5 4 7
【样例输出】
1 2
2 2
1 3

【数据规模与约定】
20%的数据满足，1 <= N <= 1 000.
100%的数据满足，1 <= N <= 100 000，0 <= Ai <= 109.

代码

不多解释，你懂的

#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <iostream>
#include <cstdlib>
#include <map>
#include <stack>
#include <set>
using namespace std;
#define MAXN 1000000 + 10
int a[MAXN], s[MAXN], t, l[MAXN], r[MAXN], n;

int main()
{
	ios::sync_with_stdio(false);
	freopen("a.in", "r", stdin);
	freopen("a.out", "w", stdout);
	cin >> n;
	for (int i = 1; i <= n; ++i) cin >> a[i];
	a[0] = a[n + 1] = INT_MAX;
	s[1] = 0, t = 1;
	for (int i = 1; i <= n; ++i)
	{
		while (a[s[t]] <= a[i]) --t;
		l[i] = s[t] + 1; s[++t] = i;
	}
	s[1] = n + 1, t = 1;
	for (int i = n; i >= 1; --i)
	{
		while (a[s[t]] <= a[i]) --t;
		r[i] = s[t] - 1; s[++t] = i;
	}
	for (int i = 1; i <= n; ++i)
		cout << l[i] << " " << r[i] << endl;
	return 0;
}