(一)单调栈查找前驱值与后继值　单调栈其实就是一个栈，并非什么新颖的数据结构，是栈结构的一种十分常用的操作，与用栈进行括号匹配、表达式求值乃至模拟递归一样，都是单调栈仅仅是一种常见的用途。　单调栈是一种满足单调性的栈结构，其维护单调性方式是弹出栈顶不符合的条件的元素，也就是说，单调栈存储的并非入栈的全部元素，相当一部分元素会被弹掉。使用单调栈通常是为了预处理算出数组每个元素的前驱值、后续值，以此优化一些问题的复杂度。此处前驱值、后继值概念与线性表中所学的概念并不相同，此处的前驱值是指其前面第一个比它更大的元素，后继值是指其后面第一个比它更大的元素。问题思路描述LC0496.下一个更大元素I维护

顾名思义单调栈就是具有单调性的栈常见模型：找出每个数左边离它最近的比它大/小的数【算法】intstk[N],tt=0; //栈中存数据for(inti=1;i>x;while(tt&&stk[tt]>=x)tt--; //左边比它小的数stk[++tt]=i; //把当前值放在合适地方}【应用一】直方图中最大的矩形算法思想:①以每一个矩形的高为标准，找出左右两边第一个小于此矩形高的矩形，枚举所有的矩形，找出最大面积。②利用单调栈，进行预处理将每个矩形左右两边的第一个小于此矩形高的矩形。#include#include#include#includeusingnamespacestd;typed

顾名思义单调栈就是具有单调性的栈常见模型：找出每个数左边离它最近的比它大/小的数【算法】intstk[N],tt=0; //栈中存数据for(inti=1;i>x;while(tt&&stk[tt]>=x)tt--; //左边比它小的数stk[++tt]=i; //把当前值放在合适地方}【应用一】直方图中最大的矩形算法思想:①以每一个矩形的高为标准，找出左右两边第一个小于此矩形高的矩形，枚举所有的矩形，找出最大面积。②利用单调栈，进行预处理将每个矩形左右两边的第一个小于此矩形高的矩形。#include#include#include#includeusingnamespacestd;typed

柱状图中最大的矩形原题：84.LargestRectangleinHistogram题目描述：给定\(n\)个非负整数，用来表示柱状图中每个柱子的高度。每个柱子相邻且宽度为1。求这个柱状图中能容纳的最大矩形的面积。思路：对于一个柱状图中的最大矩形，我们可以观察出如下性质：矩形的高必等于某个柱子的高度，也就是矩形的上边与某个柱子的上边在同一条直线上。证明：假设上述不成立。那对于每个柱子，它们的高都比这个最大矩形的高至少大1。因此我们可以增加这个矩形的高，得到一个更大的矩形，并且这个矩形还在柱状图中。因此这个矩形不是最大的矩形，得出悖论。因此此条性质成立。矩形的左边柱子的高度小于矩形高度，矩形的右

柱状图中最大的矩形原题：84.LargestRectangleinHistogram题目描述：给定\(n\)个非负整数，用来表示柱状图中每个柱子的高度。每个柱子相邻且宽度为1。求这个柱状图中能容纳的最大矩形的面积。思路：对于一个柱状图中的最大矩形，我们可以观察出如下性质：矩形的高必等于某个柱子的高度，也就是矩形的上边与某个柱子的上边在同一条直线上。证明：假设上述不成立。那对于每个柱子，它们的高都比这个最大矩形的高至少大1。因此我们可以增加这个矩形的高，得到一个更大的矩形，并且这个矩形还在柱状图中。因此这个矩形不是最大的矩形，得出悖论。因此此条性质成立。矩形的左边柱子的高度小于矩形高度，矩形的右