- 1
- 2
- 3
- 4
- 5
用单调栈求解直方图最大矩形面积的过程.docx
资料介绍
用单调栈求解直方图最大矩形面积的过程
直方图最大矩形是单调栈的经典应用,它在
时间内求解。本文从问题定义出发,详细剖析如何用单调栈确定每个柱子的左右边界,从而求出最大矩形面积。
问题定义
给定一个直方图,每根柱子有一定高度,求能在直方图中画出的最大矩形面积。矩形必须完全由柱子覆盖。
高度: [2,1,5,6,2,3]
最大矩形面积: 10(高5宽2,或高6宽1等)
朴素思路及其局限
对每根柱子作为矩形最低点,向左右扩展到"第一个比它矮"的柱子,计算以它为高的最大矩形。若对每根柱子都向两边扫描,复杂度
。
单调栈的核心思想
单调栈维护一个"高度单调递增"的栈(存下标)。关键在于:当弹出某根柱子时,它的左右边界就确定了。
· 左边界:弹出后新的栈顶(或 -1)是它左边第一个更矮的柱子。
· 右边界:当前遍历到的柱子是它右边第一个更矮的柱子。
据此即可算出该柱子的最大矩形宽度。
部分文件列表
| 文件名 | 大小 |
| 用单调栈求解直方图最大矩形面积的过程.docx | 38K |
最新上传
-
sialuoyu 打赏1.00元 3天前
-
21ic小能手 打赏5.00元 3天前
-
21ic小能手 打赏5.00元 3天前
-
他山之石可攻玉 打赏60.00元 3天前
用户:烟雨
-
江岚 打赏310.00元 3天前
用户:潇潇江南
-
21ic下载 打赏310.00元 3天前
用户:江岚
-
21ic下载 打赏310.00元 3天前
用户:潇潇江南
-
21ic下载 打赏210.00元 3天前
用户:zhengdai
-
21ic下载 打赏60.00元 3天前
用户:他山之石可攻玉
-
21ic下载 打赏60.00元 3天前
用户:烟雨
-
21ic下载 打赏110.00元 3天前
用户:w993263495
-
21ic下载 打赏60.00元 3天前
用户:gsy幸运
-
21ic下载 打赏70.00元 3天前
用户:xzxbybd
-
21ic下载 打赏20.00元 3天前
用户:kkfjenui
-
21ic下载 打赏30.00元 3天前
用户:王小琪
-
21ic下载 打赏20.00元 3天前
用户:sun2152
-
21ic下载 打赏20.00元 3天前
用户:w1966891335
-
21ic下载 打赏20.00元 3天前
用户:xuzhen1
-
21ic下载 打赏20.00元 3天前
用户:w178191520
-
21ic下载 打赏20.00元 3天前
用户:zq_1943
-
21ic下载 打赏20.00元 3天前
用户:kk1957135547
-
21ic下载 打赏25.00元 3天前
用户:铁蛋锅
-
21ic下载 打赏20.00元 3天前
用户:liqiang9090
-
21ic下载 打赏20.00元 3天前
用户:x15580286248
-
21ic下载 打赏15.00元 3天前
用户:玉落彼岸
-
21ic下载 打赏5.00元 3天前
用户:hly1230218
-
21ic下载 打赏5.00元 3天前
用户:叮当猫666
-
21ic下载 打赏5.00元 3天前
用户:xjgtgl
-
21ic下载 打赏5.00元 3天前
-
21ic下载 打赏5.00元 3天前
用户:贵平130532
-
21ic下载 打赏5.00元 3天前
用户:linyi3
-
21ic下载 打赏10.00元 3天前
用户:有理想666
-
21ic下载 打赏10.00元 3天前
用户:yahuang001
-
21ic小能手 打赏3.00元 3天前
资料:小米MIX3电路图
-
21ic小能手 打赏10.00元 3天前
-
21ic小能手 打赏5.00元 3天前
-
江岚 打赏100.00元 3天前
用户:潇潇江南
-
他山之石可攻玉 打赏50.00元 3天前
用户:烟雨
-
21ic下载 打赏1.00元 3天前
用户:王小琪
-
yahuang001 打赏3.00元 3天前




全部评论(0)