【单调栈】84. 柱状图中最大的矩形——数据结构经典问题的完整代码
时间: 2025-02-05 15:15:24 浏览: 67
【单调栈】这个题目通常是指在柱状图中找到面积最大的矩形。这是一个经典的动态规划问题,可以利用数据结构“单调栈”来解决。单调栈的主要思想是在遍历数组的过程中,维护一个递减的栈,当遇到当前元素小于栈顶元素时,说明栈内部分形成了一个连续下降序列,而这个序列对应的矩形左边界就是栈顶元素所在的位置。
以下是使用Python的一个简单实现:
```python
def largestRectangleArea(heights):
if not heights:
return 0
stack = []
max_area = 0
for i in range(len(heights)):
while stack and heights[stack[-1]] >= heights[i]:
h = heights[stack.pop()]
w = (i - stack[-1] - 1) if stack else i
max_area = max(max_area, h * w)
stack.append(i)
# 别忘了处理最后一个元素
while stack:
h = heights[stack.pop()]
w = len(heights) - stack[-1] - 1
max_area = max(max_area, h * w)
return max_area
# 示例
heights = [2,1,5,6,2,3]
print(largestRectangleArea(heights)) # 输出:10
```
在这个代码中,我们首先初始化一个空栈,并遍历每个高度值。对于每个新来的元素,如果它大于等于栈顶元素,我们就计算此时的矩形面积并更新最大面积;反之,就将栈顶元素出栈,继续寻找更大的矩形。最后别忘了处理栈中剩余的高度值,它们也可能形成矩形。
阅读全文
相关推荐















