【LeetCode 算法笔记】84. 柱状图中最大的矩形

问题描述

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

示例 1:
输入：heights = [2,1,5,6,2,3]
输出：10
解释：最大的矩形为图中红色区域，面积为 10

示例 2：
输入： heights = [2,4]
输出： 4

提示：
1 <= strs.length <= 104
0 <= strs[i].length <= 100

暴力求解：

面积 = 宽（几个数字的数量）* 高 （其中最小的数字的值）
从头开始，对于每一个元素搜索一遍后面所有的元素，输出面积最大的值。

class Solution:def largestRectangleArea(self, heights: List[int]) -> int:area = 0n = len(heights)for i in range(n):for j in range(i, n):w = j - i + 1h = min(heights[i:j+1])s = w * harea = s if s > area else areareturn area

算法复杂度：$O(N^2)$
如果 LeetCode 上提交暴力求解的代码，会因为超时不通过。

栈

创建栈，存储还无法确定边界的柱子下标。如果右边的柱子高度比栈顶矮，开始从栈顶弹出并计算面积。

class Solution:def largestRectangleArea(self, heights: List[int]) -> int:heights.append(0)   # 列尾插入哨兵stack = [-1]        # 栈首插入哨兵area = 0n = len(heights)for i in range(n):while(heights[i] < heights[stack[-1]]): k = stack.pop()left = stack[-1]width = i - left - 1s = width * heights[k]area = s if s > area else areastack.append(i)return area

算法复杂度：$O(N)$