作者介绍：10年大厂数据\经营分析经验，现任大厂数据部门负责人。
会一些的技术：数据分析、算法、SQL、大数据相关、python
欢迎加入社区：码上找工作
作者专栏每日更新：
备注说明：方便大家阅读，统一使用python，带必要注释，公众号 数据分析螺丝钉 一起打怪升级
题目描述
给定一个非负整数数组 heights，其中每个元素代表柱状图中柱子的高度，数组中每个元素的宽度都是 1。找出柱状图中能够勾勒出来的矩形的最大面积。
输入格式
- heights：一个表示柱状图高度的整数数组。
输出格式
- 返回能够勾勒出的矩形的最大面积。
示例
示例 1
输入: [2,1,5,6,2,3] 输出: 10 解释: 最大的矩形为 heights[2] 到 heights[3] 的部分，面积为 5 * 2 = 10。
示例 2
输入: [2,4] 输出: 4
方法一：暴力解法
解题步骤
- 遍历每个柱子：作为矩形的可能的高度。
- 向左右扩展：找出以当前柱子高度为高的最大宽度。
完整的规范代码
def largestRectangleArea(heights): """ 暴力解法计算柱状图中最大的矩形面积 :param heights: List[int], 柱状图的高度 :return: int, 最大矩形的面积 """ 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]) max_area = max(max_area, min_height * (j - i + 1)) return max_area # 示例调用 print(largestRectangleArea([2,1,5,6,2,3])) # 输出: 10
算法分析
- 时间复杂度：(O(n^2))，对于每个柱子，需要向右扩展以计算面积。
- 空间复杂度：(O(1))，只使用了常数空间。
方法二：单调栈
解题步骤
- 使用单调栈：维护一个单调递增的栈。
- 计算面积：当当前柱子的高度小于栈顶元素时，计算栈顶元素的最大矩形面积并出栈。
完整的规范代码
def largestRectangleArea(heights): """ 使用单调栈计算柱状图中最大的矩形面积 :param heights: List[int], 柱状图的高度 :return: int, 最大矩形的面积 """ stack = [] max_area = 0 heights = [0] + heights + [0] # 添加哨兵简化边界处理 for i in range(len(heights)): while stack and heights[stack[-1]] > heights[i]: h = heights[stack.pop()] w = i - stack[-1] - 1 max_area = max(max_area, h * w) stack.append(i) return max_area # 示例调用 print(largestRectangleArea([2,1,5,6,2,3])) # 输出: 10
算法分析
- 时间复杂度：(O(n))，每个柱子进栈和出栈各一次。
- 空间复杂度：(O(n))，栈的大小最大为 (n)。
方法三：分治算法
解题步骤
- 递归分治：找到最矮的柱子，将问题分成左右两部分。
- 计算面积：计算跨过最矮柱子的矩形面积，递归计算左右部分的最大面积。
完整的规范代码
def largestRectangleArea(heights): """ 分治算法计算柱状图中最大的矩形面积 :param heights: List[int], 柱状图的高度 :return: int, 最大矩形的面积 """ def calculateArea(start, end): if start > end: return 0 min_index = start for i in range(start, end + 1): if heights[i] < heights[min_index]: min_index = i left_area = calculateArea(start, min_index - 1) right_area = calculateArea(min_index + 1, end) cross_area = heights[min_index] * (end - start + 1) return max(left_area, right_area, cross_area) return calculateArea(0, len(heights) - 1) # 示例调用 print(largestRectangleArea([2,1,5,6,2,3])) # 输出: 10
算法分析
- 时间复杂度：平均 (O(n log n))，但最坏情况下为 (O(n^2))，当数组已经是升序或降序时。
- 空间复杂度：(O(n))，递归栈的深度。
方法四：动态规划
解题步骤
- 计算左右边界：对于每个柱子，使用动态规划计算左右两边第一个比它小的柱子的位置。
- 计算最大面积：利用上述计算的边界，可以直接计算以每个柱子为高的最大矩形面积。
完整的规范代码
def largestRectangleArea(heights): """ 动态规划计算柱状图中最大的矩形面积 :param heights: List[int], 柱状图的高度 :return: int, 最大矩形的面积 """ if not heights: return 0 n = len(heights) left = [0] * n right = [n] * n # 计算每个柱子的左边界 for i in range(n): p = i - 1 while p >= 0 and heights[p] >= heights[i]: p = left[p] - 1 left[i] = p + 1 # 计算每个柱子的右边界 for i in range(n - 1, -1, -1): p = i + 1 while p < n and heights[p] >= heights[i]: p = right[p] right[i] = p # 计算最大面积 max_area = 0 for i in range(n): max_area = max(max_area, heights[i] * (right[i] - left[i])) return max_area # 示例调用 print(largestRectangleArea([2,1,5,6,2,3])) # 输出: 10 • 1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25 • 26 • 27 • 28 • 29 • 30 • 31 • 32 • 33 • 34 • 35 • 36
算法分析
- 时间复杂度：(O(n))，三次遍历数组。
- 空间复杂度：(O(n))，用于存储左右边界的数组。
方法五：扩展中心法
解题步骤
- 遍历每个柱子：将每个柱子作为中心，向左右扩展，直到找到比它小的柱子为止。
- 计算面积：对于每个中心柱子，根据其左右边界计算面积。
完整的规范代码
def largestRectangleArea(heights): """ 扩展中心法计算柱状图中最大的矩形面积 :param heights: List[int], 柱状图的高度 :return: int, 最大矩形的面积 """ n = len(heights) max_area = 0 for i in range(n): left, right = i, i while left > 0 and heights[left - 1] >= heights[i]: left -= 1 while right < n - 1 and heights[right + 1] >= heights[i]: right += 1 max_area = max(max_area, heights[i] * (right - left + 1)) return max_area # 示例调用 print(largestRectangleArea([2,1,5,6,2,3])) # 输出: 10
算法分析
- 时间复杂度：平均 (O(n))。但最坏情况下，当所有元素相等时，每次中心扩展的复杂度为 (O(n))，总复杂度为 (O(n^2))。
- 空间复杂度：(O(1))，只使用常量额外空间。
不同算法的优劣势对比
| 特征 | 方法一：暴力解法 | 方法二：单调栈 | 方法三：分治算法 | 方法四：动态规划 | 方法五：扩展中心法 |
| 时间复杂度 | (O(n^2)) | (O(n)) | 平均 (O(n log n)), 最坏 (O(n^2)) | (O(n)) | 平均 (O(n)), 最坏 (O(n^2)) |
| 空间复杂度 | (O(1)) | (O(n)) | (O(n)) | (O(n)) | (O(1)) |
| 优势 | 简单易实现 | 高效，适用于大多数情况 | 对特定情况优化良好 | 高效，适用于所有情况 | 简单直观 |
| 劣势 | 时间复杂度高 | 空间消耗较大 | 复杂且可能导致性能问题 | 空间消耗 | 性能不稳定 |
应用示例
计算几何：在计算几何和图形设计中，可能需要计算多种形状的最大面积或相似的度量。
资源优化问题：在资源分配和生产线管理中，可能需要优化给定资源的布局以最大化效率或利润。
游戏开发：在游戏开发中，可能需要计算或优化地图区域中的某些特定区域，以增强游戏的策略性或视觉效果。
欢迎关注微信公众号 数据分析螺丝钉
