22 | 栈与单调栈：最大矩形面积

作业打卡： #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缓存的友好性等适用不同的生产环境。但对同一组数据进行这种多个数组的操作，其实都是在模拟函数了，就和我们平时在实验室做数学推导一个道理了，把变量（数组）做好注释，把公式写出来或者画个图就好理解了。

括号的左半部分是入栈，右半部分是出栈，符合这个规律的就是合法序列，否则就是非法的。

老师，第二行：#define max(a, b) ((a) > (b) : (a) : (b)) 应该是：#define max(a, b) ((a) > (b) ？ (a) : (b)) 老师你快醒醒啊，周六了不用工作了！！

Leetcode 题号：有效的括号--20、柱状图中最大的矩形--84。 好久以前用python做过第一题，现在早忘了哈哈~ 思考： 1，加入数组两端的‘-1’就是传说中的哨兵技巧，加入哨兵可以减少边界条件的判断，简化编程难度（JKSJ-数据结构与算法之美，第7讲）。 2，道理我都懂，单调队列单调栈很好理解，唯一的问题，就是代码看不懂（bonehead! bonehead!)！啊！中间一段时间没看，突然就懂了！！！厉害了！ 3，老师，你快醒醒！第6行，应该是 h 吧哈哈！

有效括号这个就是 leetcode https://leetcode-cn.com/problems/valid-parentheses/ 这道题，但是没有用到单调栈的性质啊

茶艺师学编程 课文例子 完整可运行代码： #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; }

茶艺师学编程 思考题 我也是想了很久才明白，这样的完全包含的序列，要用单调栈来解决，就像是在玩俄罗斯方块，配对的消失（离开栈），合法的序列在进入这个栈后为“空”，不合法的还是会有东西剩下。 代码如下： #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; }

有入口、有出口，先进先出效率高；有入口，入口即出口，先进后出/后进先出效率高。只有一个口子就不能考虑两边同时进行的状态，解决单向问题如果不能环回流动就只能先进后出或者后进先出。 当然怎么做都会把问题解决，但是就像胡老师刚开始就说的把一个水缸打满，用一桶一桶的提回来和一勺子一勺的盛回来的效率是不一样的。问题小、算法高仅能体现思维水平不同，问题大、用算法解决实际问题的时空复杂度简洁就不是仅仅体现思维水平的问题了，大问题用小问题是堆不出来——多少辆马车加一起也得不到一架火箭，那就是天壤之别了。