LeetCode 84. Largest Rectangle in Histogram 题解

LeetCode 84. Largest Rectangle in Histogram 题解题目描述给定 n 个非负整数用来表示柱状图中各个柱子的高度。每个柱子彼此相邻且宽度为 1 。求在该柱状图中能够勾勒出来的矩形的最大面积。示例 1输入heights [2,1,5,6,2,3] 输出10 解释最大的矩形为图中红色区域面积为 10示例 2输入heights [2,4] 输出4解题思路这是一个经典的单调栈问题。对于每个柱子我们需要找到左边第一个高度小于当前柱子的位置右边第一个高度小于当前柱子的位置这样以当前柱子为高的矩形宽度就是右边界 - 左边界 - 1代码实现方法一单调栈def largestRectangleArea(heights): n len(heights) # 使用单调递增栈 stack [] max_area 0 for i in range(n): # 当当前高度小于栈顶高度时计算栈顶柱子的面积 while stack and heights[i] heights[stack[-1]]: height heights[stack.pop()] # 计算宽度 width i if not stack else i - stack[-1] - 1 max_area max(max_area, height * width) stack.append(i) # 处理栈中剩余的柱子 while stack: height heights[stack.pop()] width n if not stack else n - stack[-1] - 1 max_area max(max_area, height * width) return max_area方法二哨兵法简化代码def largestRectangleArea(heights): # 在两端添加高度为 0 的哨兵 heights [0] heights [0] n len(heights) stack [] max_area 0 for i in range(n): while stack and heights[i] heights[stack[-1]]: height heights[stack.pop()] width i - stack[-1] - 1 max_area max(max_area, height * width) stack.append(i) return max_area复杂度分析时间复杂度O(n)每个元素最多入栈和出栈一次空间复杂度O(n)栈的空间算法原理为什么使用单调栈单调栈可以高效地找到每个元素左边和右边第一个比它小的元素的位置。当遇到一个更小的元素时栈顶元素的右边界就确定了栈顶元素出栈后新的栈顶就是它的左边界矩形面积计算高度当前柱子的高度宽度右边界 - 左边界 - 1测试案例# 测试案例 1 assert largestRectangleArea([2,1,5,6,2,3]) 10 # 测试案例 2 assert largestRectangleArea([2,4]) 4 # 测试案例 3 assert largestRectangleArea([2,1,2]) 3 # 测试案例 4 assert largestRectangleArea([1,1,1,1]) 4 # 测试案例 5 assert largestRectangleArea([]) 0总结本题是单调栈的经典应用也是面试中的高频题目。关键点单调递增栈栈中元素的高度递增找到每个柱子的左右边界计算以每个柱子为高的矩形面积通过本题可以深入理解单调栈在解决下一个更小/更大元素类问题中的应用。