使用单调栈来解决的一些问题
2022-09-04 12:50:34 0 举报
博客见：https://www.cnblogs.com/greyzeng/p/16654877.html
作者其他创作
大纲/内容
D
2下标（4）
1 < 4，所以此时要出栈，由于2下标压着1下标，所以4左边离它最近的比它小的数是3。4右边离它最近的比它小的数就是当前要入栈的3下标的1。
2
1下标（3）
1 < 3，所以此时要出栈，由于1下标没有压着元素，所以3左边离它最近的比它小的数不存在，-1。3右边离它最近的比它小的数就是当前要入栈的3下标的1。
3下标（1）
G
F
3
B
E
6
A
C
必须以2为右边界，得到的最大矩形
子数组累加和乘以子数组最小值所得到的结果最大是多少牛客：https://www.nowcoder.com/questionTerminal/e6e57ef2771541dfa2f1720e50bebc9a
0下标
3 < 5，所以此时要出栈，由于5没有压着栈元素，所以5左边离它最近的比它小的数不存在-1。5右边离它最近的比它小的数就是当前要入栈的1下标的3。
0下标（5）
H
必须以2为右边界，得到的最大矩形如上图绿色部分
初始状态，0号下标直接入栈
5
满足入栈条件，直接入栈
元素全部入栈完毕，此时3下标没有压着元素，也没有使得它弹出的元素，所以1左右两边离它最近的比它小的数都不存在
以 2 为例，左侧比它小的离它最近的是1
1
直方图最大矩形的面积：https://leetcode.cn/problems/largest-rectangle-in-histogram/
对 D 这个元素来说，如果 A 和 F 是 D 左右两侧比它小的离它最近的元素，那么以 D 为最小值，可以扩散的最大区间和是 B + C + D + E 的累加和。
0 条评论
回复 删除
下一页
