柱状图中最大的矩形

题目描述

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1。求在该柱状图中，能够勾勒出来的矩形的最大面积。

示例

示例 1

输入:
heights = [2,1,5,6,2,3]
输出:
10
解释:
最大的矩形为红色区域，高度为5，宽度为2，面积为10

示例 2

输入:
heights = [2,4]
输出:
4
解释:
最大矩形可以是高度4宽度1，或高度2宽度2

提示

• 1 <= heights.length <= 10^5
• 0 <= heights[i] <= 10^4

解法思路

单调栈解法

1. 核心思想：对于每个柱子，找到左右第一个比它矮的柱子作为边界

2. 算法步骤：

   • 初始化栈和最大面积变量
   • 遍历柱状图：
     • 当栈不为空且当前柱子高度 < 栈顶柱子高度：
       • 弹出栈顶作为计算高度
       • 计算宽度 = 当前索引 - 新栈顶索引 - 1
       • 更新最大面积
     • 当前索引入栈
   • 处理栈中剩余柱子

3. 复杂度分析：

   • 时间复杂度：O(n)
   • 空间复杂度：O(n)