- 1
- 2
- 3
- 4
- 5
动态规划中的单调栈优化与最大矩形问题.docx
资料介绍
动态规划中的单调栈优化DP:直方图与最大矩形
单调栈前文已介绍其基本应用(直方图最大矩形、最近更大元素)。本文深入单调栈优化DP:如何用单调栈加速某些DP的转移。单调栈利用"决策点单调"或"维护单调候选"来优化转移,是DP优化的一种重要手段。
单调栈与DP优化的联系
单调栈优化DP适用于:转移需要"在满足某单调条件的候选集合中选最优",且候选的淘汰/更新满足单调性。
经典场景:求"以每个元素为基准,向左右扩展的最大范围",这类问题用单调栈
确定每个元素的边界,再配合DP/贪心求解。
c
// 单调栈确定"左右边界"
// 对每个元素,找左边第一个小于它的位置、右边第一个小于它的位置
// 单调栈O(n)求出
这类"边界确定"是单调栈优化DP的基础。
直方图最大矩形
直方图最大矩形(前文已详述)是单调栈的经典应用:求直方图中能画出的最大矩形面积。
思路:对每根柱子,用单调栈找"左右第一个比它矮"的位置,确定以它为高的最大矩形宽度,取面积最大值。
c
// 直方图最大矩形(单调栈)
int largestRectangleArea(vector<int>& h) {
int n = h.size(), ans = 0;
stack<int> st; // 单调递增栈(存下标)
for (int i = 0; i <= n; i++) {
部分文件列表
| 文件名 | 大小 |
| 动态规划中的单调栈优化与最大矩形问题.docx | 39K |
最新上传
-
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)