思路
1.枚举 + 两遍单调栈
一个比较直接的思路是:直接枚举每个柱子i,考虑以h[i]为高度的最大面积。
高度确定了,位置也确定了,怎么计算以h[i]为高度的最大宽度呢?
很简单,往左找第一个比它矮的柱子的位置,再往右找第一个比它矮的柱子的位置。因为只有比它矮的位置会把这个高度截断👇
P4082.柱状图中最大的矩形
Leetcode 84.柱状图中最大的矩形-原题链接
题目内容
给定 n 个非负整数,用来表示柱状图中各个柱子的高度。每个柱子彼此相邻,且宽度为1。
求在该柱状图中,能够勾勒出来的矩形的最大面积。
输入描述
输入n个非负整数
输出描述
输出一个整数表示矩形最大面积
样例1
输入
2 1 5 6 2 3
输出
10

说明
最大的矩形为图中红色区域,面积为 10
样例2
输入
2 4
输出
4
说明

提示:
- 1<=heights.length<=105
- 0<=heights[i]<=104