推荐星级:
  • 1
  • 2
  • 3
  • 4
  • 5

动态规划中的单调栈优化与最大矩形问题.docx

更新时间:2026-10-13 20:21:18 大小:39K 上传用户:江岚查看TA发布的资源 标签:动态规划单调栈最大矩形DP优化直方图 下载积分:2分 评价赚积分 (如何评价?) 打赏 收藏 评论(0) 举报

资料介绍

动态规划中的单调栈优化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

全部评论(0)

暂无评论

上传资源 上传优质资源有赏金

  • 打赏
  • 30日榜单

推荐下载