day60 | 84.柱状图中最大的矩形、反思

**Day60 |84. 柱状图中最大的矩形**

在本文中，我们将讨论一个经典的问题：给定一个柱状图，如何找到其中最大的矩形。这个问题看似简单，但实际上需要一些技巧和算法来解决。

**问题描述**

假设我们有一个柱状图，每个柱子代表某一天的销售额或其他指标。我们想找出柱状图中最大的矩形，哪怕它不是完全覆盖整个图表。

**示例**

例如，我们有如下柱状图：

| 天数 | 销售额 |
| --- | --- |
|1 |10 |
|2 |20 |
|3 |15 |
|4 |25 |
|5 |30 |

在这个例子中，最大的矩形是从天数2 到天数4 的矩形，它的面积为75。

**解决方案**

为了解决这个问题，我们可以使用一个叫做「柱状图中最大的矩形」的算法。这个算法基于以下观察：

* 最大的矩形一定是以某个柱子的顶点为左下角和右上角的。
* 每个柱子都可能成为左下角或右上角。

因此，我们可以遍历每个柱子，并计算从该柱子开始的最大矩形面积。我们使用一个变量 `max_area` 来存储当前最大的矩形面积。

**代码示例**

def max_rectangle_area(heights):
 """
 计算柱状图中最大的矩形面积。
 :param heights: 柱状图的高度列表。
 :return: 最大的矩形面积。
 """
 stack = [] # 栈用于存储柱子的索引 max_area =0 # 当前最大矩形面积 for i, height in enumerate(heights):
 # 如果栈不空且当前高度小于或等于栈顶元素的高度，则弹出栈顶元素 while stack and heights[stack[-1]] >= height:
 h = heights[stack.pop()]
 # 计算从栈顶元素开始的矩形面积 w = i if not stack else i - stack[-1] -1 max_area = max(max_area, h * w)
 # 将当前索引压入栈中 stack.append(i)
 # 处理剩余柱子 while stack:
 h = heights[stack.pop()]
 w = len(heights) if not stack else len(heights) - stack[-1] -1 max_area = max(max_area, h * w)
 return max_area# 测试用例heights = [10,20,15,25,30]
print(max_rectangle_area(heights)) # 输出:75