84. 柱状图中最大的矩形

From
Leetcode
Status
回头复习下
Date
Apr 30, 2024
Tags
单调栈
Difficulty
困难
Link
https://leetcode.cn/problems/largest-rectangle-in-histogram/description/

题面

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。
示例 1:
notion image
示例 2：
notion image
提示：
  • 1 <= heights.length <=105
  • 0 <= heights[i] <= 104
 

思路

用动态规划的话，求左边第一个小于的似乎没有明显的O(1)递归关系。。。
 

题解

Loading...
目录
目录