你好，我是胡光，欢迎回来。
上节课我们讲了单调队列这种具有单调性的结构，并且说明了单调队列适合：维护队列处理顺序中的区间最大值，并且我还提到单调队列只是一个铺垫，搞清楚了单调队列的内容，才能更好地学习新的数据结构。
今天我将带你学习一种队列和单调队列的兄弟数据结构，它的性质也很有趣，就是：栈与单调栈。学习这个数据结构的时候呢，我还是要再次强调一下那句话：数据结构，就是定义一种性质，并且维护这种性质。
今日任务
在正式开始学习之前呢，先来看一下今天这 10 分钟的任务吧。
假设有一面木板墙，每块木板的宽度都是 1，你现在想在木板墙上，沿着平行于地面的方向，切割出一块矩形区域。问题来了，如果给出了每一块木板的高度，那么如何切出面积最大的矩形区域？矩形木板墙如下图所示：
如你所见，图中有 7 块木板，每块木板的高度分别为：2、1、4、5、1、3、3。经过尝试，我们发现最大矩形就是红色阴影部分所示，也就是切割了高度为 4和5 两块木板，形成了一个高度为4，宽度为2的矩形区域，这个最大面积为 8。
显而易见的结论：就是切下来的最大的矩形，一定是以最大矩形所在区域最短那块木板作为其高度值。如果不是这样的话，我们就可以提升一点点高度，让切下来的部分更大一点儿。
有了如上这个结论，我们就可以枚举每一块木板，每次都以当前木板作为高度，就是把当前这块木板，当成是切出来的矩形区域中的最矮的木板，然后向左边和右边分别做延伸，切出此时的最大矩形区域。当把所有木板都试过一遍后，我们在所有枚举结果中比较出最大值，这个最大值就是我们要求的最大矩形面积。如果木板的个数为 n，那这种做法的时间复杂度接近于 $O(n^2)$。
而今天，我要给你讲的方法，能将这个时间复杂度降低到 $O(n)$，这种结构方法就像我们上次讲的单调队列一样有趣。接下来，就让我们一点点地揭开这个结构神秘的面纱。
必知必会，查缺补漏
想要完成今天这个任务呢，你必须掌握接下来我要教给你的一个新的数据结构：单调栈。
1.栈：维护一种完全包含关系的结构
首先让我们来认识一下最简单的栈结构，所谓栈结构，你可以想象成只有一个口的羽毛球桶，羽毛球只能从唯一的一个口放入和取出。我们把编号1、2、3三个羽毛球按顺序放进球桶后，如果想取出来，那么这些球被取出来的顺序一定是编号3、2、1。也就是说后放入的羽毛球，在取出的时候，会最先被取出来，它们放入和取出的顺序是相反的。
如果说，上一节我们学习的队列结构是先进先出的结构，那么今天我们学习的栈就是一种后进先出的结构。栈和队列一样，都是计算机中，用来规范处理顺序的基础结构。
图中所示，入栈顺序分别是 蓝、绿、红，那么出栈顺序就一定是红、绿、蓝。图中每一个颜色的方块上标注的数字，就是每一个方块入栈及出栈的顺序。
从示意图中，我们还可以观察到一个有趣的事情，在顺序上而言，红色方块被绿色方块包裹着，绿色方块被蓝色方块包裹着。这种结构，像是程序的调用过程，如果把蓝色方块，看成是主函数的话，那么绿色方块就是主函数中调用的一个函数 A，红色方块就是 A 函数中调用的另外一个函数 B，三个函数调用的顺序是主函数、函数 A、函数 B。
而它们的执行结束顺序恰恰是相反的，首先是 函数 B 结束，然后是 函数 A 结束，最后是主函数结束。实际上，我们计算机用来维护函数执行的底层系统，就是用的这种栈结构。
你可以认为，栈结构本身维护的是一种完全包含关系。其实函数之间的运行，就是一种完全包含关系，只要在主函数中调用函数 B，那么函数 B 一定在主函数结束之前结束，这就可以视为是主函数包含函数 B。
2.单调栈：维护最近大于或小于关系的结构
我们了解了最简单的栈结构以后，接下来，就来让我们学习一种栈的升级产物：单调栈。理解单调栈的最简单方法，就是基于对单调队列的理解去学习它。如果你单调队列还没有掌握，那我建议你再好好看一看上节课中关于单调队列的相关内容。
我先问你一个问题，队列结构和栈结构到底有什么区别？你可能会说，它们唯一的区别就是，队列是从一端进另外一端出，栈是在同一端进出。
那我再问你一个问题，堵住出口的单调队列，和栈有什么区别？你会发现，好像没什么区别了，单调队列为了维护单调性，在入队列的时候，也会将违反单调性的元素弹出，所以，这就相当于栈的从同一端进出。
好了，如果你明白这些问题，我可以明确地告诉你：堵住出口的单调队列，就是我们今天要学习的“单调栈”。
既然堵住了单调队列的出口，那么这种所谓单调栈的结构，就再也维护不了区间最大值了。那它维护的是什么呢？让我们以单调递减栈为例。
如图所示，这是我假设的一种单调栈中元素的情况：序列第 12 号元素入栈以后，单调栈中只剩下了 4 个元素，从栈底到栈顶，值分别为23、18、15 和 9，分别对应了原序列的第 2 号、第 5 号，第 9 号 以及 第 12 号。
关于单调栈性质的思考，我们只需要重点关注栈顶的 12 号元素和 9 号元素之间的关系即可。如果 12 号元素入栈以后，为了保持栈中的单调递减性，它最终放在了 9 号元素上面，那说明什么呢？是不是说明从 9 号元素到 12 号之间的元素值，均小于 12 号元素值呢？也就是说，10号、11 号这两个元素的值，我们虽然不知道具体是多少，可这两个元素的值，肯定比 9 号元素小，甚至也比 12 号元素小。否则，按照单调栈的入栈规则，12 号元素和 9 号元素就不可能在栈中相邻。
其实，说到这里，你应该已经对单调栈的性质有所感觉了。如果我们将一个元素压入单调递减栈，那么这个元素会落在离它最近，且比它大的元素上面。就像上面的例子中，当12号元素入栈以后，它落在了9号元素上面，说明从 12 号元素向前找，9 号元素是第一个比 12 号元素值大的元素。
如果说单调队列是维护区间最值的高效结构，单调栈就是维护最近大于或小于关系的高效结构。如果想要维护最近大于关系，就建立一个单调递减栈，然后将每个元素依次入栈，在这个过程中，我们就可以统计得到每一个元素之前离它最近的，且大于它的元素。那要是想维护最近小于关系呢？就建立一个单调递增栈就好了！
至此，我们就掌握了单调栈的基本性质了。
一起动手，搞事情
今天的思考题呢，跟括号匹配有关系。任务很简单，就是给你一串括号序列，括号序列中可能包含小括号()，中括号[] 或者 大括号{}，你需要写程序，判断这个括号序列是否合法。只要括号之间，没有交错重叠的情况，就是合法的括号序列。
下列给出了一些合法的序列的示例：
({})
[]([]){()}
下面是一些非法的括号序列的示例：
([)]
(((){}
通过观察括号序列，你会发现合法的括号序列，其实就是一种完全包含的结构，关于这种结构合法性的判断，和我们今天讲的栈结构有什么关系呢？开动你聪明的大脑，思考一下吧！
最大矩形面积
最后我们回到今天的任务，先来回顾一下之前所说的解题过程：我们通过枚举每一块木板作为切割出的木板墙的高度，每次都需要向左边和右边分别做查找，一直找到一块高度小于当前木板高度的位置，这样就确定了切割木板墙的长度。
以图1中高度为4的木板为例，我们通过向左延伸查找，发现左边第一块就比它短，这样就确定了向左延伸的长度是0；往右延伸查找，发现第二块木板比它短，也就是向右延伸的长度是1。说到这里，你会发现，上面这个过程，不就是我们之前所说的，维护最近小于关系么！只需要建立一个单调递增栈，就可以完成这个任务！
下面，是一份我给出的示例代码：
#define MAX_N 1000
#define max(a, b) ((a) > (b) ？ (a) : (b))
int s[MAX_N + 5], top;
int l[MAX_N + 5], r[MAX_N + 5];
int max_matrix_area(int *h, int n) {
h[0] = h[n + 1] = -1;
top = -1, s[++top] = 0;
// 找到每一块木板，左边第一块比其矮的木板编号
for (int i = 1; i <= n; i++) {
while (top >= 0 && h[s[top]] >= h[i]) --top;
l[i] = s[top];
s[++top] = i;
}
// 找到每一块木板，右边第一块比其矮的木板编号
top = -1, s[++top] = n + 1;
for (int i = n; i >= 1; i--) {
while (top >= 0 && h[s[top]] >= h[i]) --top;
r[i] = s[top];
s[++top] = i;
}
// 在所有木板中，找到面积最大的矩形
int ans = 0;
for (int i = 1; i <= n; i++) {
ans = max(ans, (r[i] - l[r] - 1) * h[i]);
}
return ans;
}
如上代码所示，max_matrix_area 函数传入两个参数，木板高度数组首地址 h，和木板数量 n。代码中的 s 数组，后续的作用就是模拟单调栈，top 代表了栈顶元素的下标。
你需要注意的是，代码中假设木板的编号是从 1 到 n 的，然后，在数组的 0 位 及 n + 1 位分别加入两块高度为 -1 的虚拟木板，这是边界控制的一种技巧。也就是说，在每块木板向左搜索的时候，最远也就搜索到 0 号位就停止了，向右搜索的时候呢，最远搜索到 n + 1 位也就停止了。通过加入虚拟木板，代码中就少了相关的边界条件判断，这是一种很实用的技巧，你一定要理解和掌握。
课程小结
以上就是我们今天要学习的单调栈的内容，关于单调栈，其实你只需要对比着单调队列进行学习和记忆即可，记住以下两点：
- 单调栈是用来维护最近大于或小于关系的数据结构。
- 单调栈就是堵住出口的单调队列，所以其时间复杂度与单调队列一致，平均到每个处理元素上，都是 $O(1)$ 的时间复杂度。
好了，单调栈的知识，就讲到这里了。我是胡光，我们下期见。
精选留言
2020-03-08 15:53:32
#define MAX 1000
char stack[MAX];
int top = 0;
int f(char* s){
if( s == NULL )
return false;
for( int i=0; s[i]!='\0'; i++)
{
if(s[i]=='(' || s[i]=='[' || s[i]=='{')
stack[++top] = s[i];
else if( (s[i]==')'&&stack[top]=='(') || (s[i]==']'&&stack[top]=='[') || (s[i]=='}'&&stack[top]=='{') )
top--;
else
return -1;
}
if( top == 0 )
return 0;
return -1;
}
其实上一节和这一节都是用到了两个数组，分别处理值和对应的输入数据的下标，相当于维护了一个单调性的函数映射。而且还是一个分区间的分段函数，其实想通了这个示例代码就很好看了，数组和链表（指针或引用）是最基础的数据结构，其他数据结构也是通过结构体或类来吧数组和链表进行新的组合，而数组和链表在权衡随机访问和插入的时间复杂度和空间复杂度，对cpu缓存的友好性等适用不同的生产环境。但对同一组数据进行这种多个数组的操作，其实都是在模拟函数了，就和我们平时在实验室做数学推导一个道理了，把变量（数组）做好注释，把公式写出来或者画个图就好理解了。
2020-10-12 14:34:36
课文例子 完整可运行代码：
#include <stdio.h>
#define MAX_N 1000
#define max(a, b) ((a) > (b) ? (a) : (b))
int s[MAX_N + 5], top;
int l[MAX_N + 5], r[MAX_N + 5];
int max_matrix_area (int *h, int n){
h[0] = h[n + 1] = -1;
top = -1, s[++top] = 0;
for (int i = 1; i <= n; i++){
while (top >= 0 && h[s[top]] >= h[i])--top;
l[i] = s[top];
s[++top] = i;
}
top = -1, s[++top] = n + 1;
for (int i = n; i >= 1; i--){
while (top >=0 && h[s[top]] >= h[i])--top;
r[i] = s[top];
s[++top] = i;
}
int ans = 0;
for (int i = 1; i <= n; i++){
ans = max(ans, (r[i] - l[i] - 1) * h[i] );
}
return ans;
}
int main(){
int h[7] = {2, 1, 4, 5, 1, 3, 3};
int n = 7;
int a;
a = max_matrix_area(h, n);
printf("最大面积为：%d", a);
return 0;
}
2020-10-13 14:13:40
思考题
我也是想了很久才明白，这样的完全包含的序列，要用单调栈来解决，就像是在玩俄罗斯方块，配对的消失（离开栈），合法的序列在进入这个栈后为“空”，不合法的还是会有东西剩下。
代码如下：
#include <stdio.h>
#define A (a[i] == '(')
#define AA ((a[i-1] == '(' ) && ( a[i] == ')'))
#define B (a[i] == '[')
#define BB ((a[i-1] == '[' ) && ( a[i] == ']'))
#define C (a[i] == '{')
#define CC ((a[i-1] == '{' ) && ( a[i] == '}'))
char a[500] = {0};
int test(char *a){
int b[1000] = {0};
int top = 0;
for (int i = 0; a[i] != '\0' ; i++){
if( A || B || C){
b[++top] = i;
if( AA || BB || CC){
top -= 2;
}
}
}
return top;
}
int main(){
puts("please input:");
scanf("%c", &a);
int c = 0;
c = test(a);
if ( c == 0 )puts("该序列是合法的。");
else puts("该序列不合法。");
return 0;
}
2020-04-19 00:14:45
当然怎么做都会把问题解决，但是就像胡老师刚开始就说的把一个水缸打满，用一桶一桶的提回来和一勺子一勺的盛回来的效率是不一样的。问题小、算法高仅能体现思维水平不同，问题大、用算法解决实际问题的时空复杂度简洁就不是仅仅体现思维水平的问题了，大问题用小问题是堆不出来——多少辆马车加一起也得不到一架火箭，那就是天壤之别了。
2020-03-11 00:43:02
2020-03-07 20:47:45
应该是：#define max(a, b) ((a) > (b) ？ (a) : (b))
老师你快醒醒啊，周六了不用工作了！！
2020-03-07 20:29:39
好久以前用python做过第一题，现在早忘了哈哈~
思考：
1，加入数组两端的‘-1’就是传说中的哨兵技巧，加入哨兵可以减少边界条件的判断，简化编程难度（JKSJ-数据结构与算法之美，第7讲）。
2，道理我都懂，单调队列单调栈很好理解，唯一的问题，就是代码看不懂（bonehead! bonehead!)！啊！中间一段时间没看，突然就懂了！！！厉害了！
3，老师，你快醒醒！第6行，应该是 h 吧哈哈！
2020-03-07 12:26:55