关于设置关注可见

设置这个就是为了卡一下网上的各种搬运，可以关注之后再取关，这样就可以看了hh

0.序

如果在这一块遇见啥问题可以留言讨论

while(keep) ability++;

1. 前言

对刚开始学算法与数据结构的人来说，栈应该是首先要接触的东西(或者是数组or链表)。然而栈虽然是最先学的，但并不是说就很简单
=。=。。。毕竟基础(base) $\ne$ 简单(easy)

栈

概念

首先我们知道：

• 栈是一个线性的数据结构(应该很好懂)，同时栈是一个受限制的线性数据结构。
• 我们只能在一端添加和删除元素，而另一端啥都不能干(显得肥肠的无用)。
• 能进行操作的一端称为栈顶，另一端称为栈底。
• 这时我们就能发现，这是一个后进先出的结构，先进去的会被压在下面，后进去的会在上面。而又只能从上面进出，所以后进的会先出来。

栈的操作

• 添加
• 删除
  (在上面已经提到了hh)

关于实现一个栈

栈的实现形式大概上有两种——数组，链表
top：记录栈顶的位置，在push的时候选择先++这样下标从1开始（个人习惯而已啦。。）

int stack[100000], top = 0;void push(int x) {stack[++top] = x;}int pop() {return stack[top--];}

如果你是高贵的带模板的语言的用户 such as C++

stack s;s.pop();s.push(x);

举个栗子

#include #include #include #include const int N_MAX = 100000 + 10;using namespace std;int m;int s[N_MAX], top = 0;void push(int x) {s[++top] = x;}int pop() {return s[top--];}int main(){    cin >> m;    while (m--) { string c; cin >> c; if (c == "push") { // 向栈顶插入一个数 x     int x;     cin >> x;     push(x); } else if (c == "pop") { // 从栈顶弹出一个数     if (top) {     // 记得判断top是否等于0，等于零的话栈就是空了  pop();     } } else if (c == "empty") { // 判断栈是否为空     if (top) {  cout << "NO\n";     }     else {  cout << "YES\n";     } } else { // 查询栈顶元素     cout << s[top] << endl; }    }    return 0;}

一点高级的东西——单调栈

有些时候我们需要一些具有特殊性质的栈，来更好的完成题目要求。

举个栗子

给定一个长度为 $N$ 的整数数列，输出每个数左边第一个比它小的数，如果不存在则输出 $-1$。

输入格式

第一行包含整数 $N$，表示数列长度。

第二行包含 $N$ 个整数，表示整数数列。

输出格式

共一行，包含 $N$ 个整数，其中第 $i$ 个数表示第 $i$ 个数的左边第一个比它小的数，如果不存在则输出 $-1$。

数据范围

1 ≤ N ≤ 1 0 5 1≤N≤10^5 1≤N≤105
1 ≤ 数 列 中 元 素 ≤ 1 0 9 1≤数列中元素≤10^9 1≤数列中元素≤109

输入样例：

53 4 2 7 5

输出样例：

-1 3 -1 2 2

首先我们可以很快的写出一个时间复杂度为 O ( n 2 ) O(n^2) O(n2) 的暴力算法
他长这个样子

#include #include const int N_MAX = 1000000 + 10;using namespace std;int s[N_MAX], top = 0;int n, a[N_MAX];int ans[N_MAX];int main() {cin >> n;for (int i = 1; i > a[i];ans[i] = -1;}for (int i = 1; i =1; j--) {if (a[i] > a[j]) {ans[i] = a[j];break;}}}for (int i = 1; i <= n; i++) {cout << ans[i] << ' ';}}

写完之后一看数据范围：$100000$
=。=。。。这显然是不能通过的

现在我们来引入单调栈

啥叫单调栈

顾名思义啊，就是栈里的元素是单调递增或者单调递减的，所以叫他单调栈。
这里我们用到的是单调递增栈。

为啥要用单调栈

因为…单调栈的复杂度是 $O(n)$的，可以肥肠愉悦的通过 1 0 5 10^5 105的数据范围

为啥会是$O(n)$嘞

可以这样想，在顺序遍历数组的时候，假设我们遍历到了第$i$个数$a[i]$，我们可以把它加入单调栈
遍历到$i+1$时，如果$a[i]$在栈内，我们就可以判断$a[i$]是不是$a[i+1]$左边的最小元素
如果是的话答案就是$a[i]$，然后把$a[i+1]$入栈，如果不是就将$a[i+1]$弹出，判断下一个元素。这样操作的话就可以在一次遍历内完成这个问题

怎么搞一个单调栈

在保持栈内元素单调递增/单调递减的前提下（如果栈顶元素大于要入栈的元素，将将其弹出），将新元素入栈。

这样的话就可以写出这样的一段code

#include #include #include #include const int N_MAX = 500000 + 10;using namespace std;int s[N_MAX], top, n;int main() {scanf("%d", &n);for (int i = 1; i = x) {top--;}if (top) {printf("%d ", s[top]);}else {printf("-1 ");}s[++top] = x;}}