### Python 实现直方图最大矩形面积算法 以下是基于栈的方法来解决直方图中最大矩形面积问题的 Python 实现。这种方法的时间复杂度为 O(n)，因为它只需要遍历一次数组并利用栈结构记录柱状图的高度及其索引。 ```python def largest_rectangle_area(heights): stack = [] # 使用栈存储柱子的索引 max_area = 0 heights.append(0) # 添加哨兵节点，确保最后能够清空栈 for i in range(len(heights)): while stack and heights[stack[-1]] >= heights[i]: h = heights[stack.pop()] # 当前高度 w = i if not stack else i - stack[-1] - 1 # 宽度计算取决于当前索引和栈顶索引 max_area = max(max_area, h * w) # 更新最大面积 stack.append(i) return max_area # 测试用例 print(largest_rectangle_area([2, 1, 5, 6, 2, 3])) # 输出应为 10 ``` #### 解释 上述代码的核心逻辑如下： - **栈的作用**：用于保存柱子的索引，并保持这些柱子的高度单调递增。 - **宽度计算**：当遇到一个比栈顶柱子低的新柱子时，弹出栈顶元素并计算以其高度为基础的最大矩形面积。此时，宽度由当前索引 `i` 和新的栈顶索引决定[^3]。 - **哨兵机制**：为了简化处理，在输入列表末尾追加一个零值，这样可以保证所有柱子都会被弹出栈进行面积计算。 此方法相较于暴力枚举的方式更加高效，适合大规模数据集下的应用。 --- ### 另一种双层循环实现方式 如果希望理解更简单的思路，则可以通过双重循环逐一尝试每种可能性： ```python def brute_force_largest_rectangle_area(heights): max_area = 0 n = len(heights) for i in range(n): min_height = float('inf') for j in range(i, n): min_height = min(min_height, heights[j]) current_area = min_height * (j - i + 1) max_area = max(max_area, current_area) return max_area # 测试用例 print(brute_force_largest_rectangle_area([2, 1, 5, 6, 2, 3])) # 输出应为 10 ``` 这种实现虽然易于理解和编写，但由于其时间复杂度为 O(n²)，对于较大的输入可能会显得效率低下[^1]。 --- ### 性能对比分析 两种方法各有优劣： - 基于栈的方法具有线性时间复杂度 O(n)，适用于大多数实际场景。 - 暴力法简单直观，但在性能上受限于嵌套循环带来的高开销。 因此推荐优先采用基于栈的技术方案以获得更好的运行表现[^3]。