给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。求在该柱状图中，能够勾勒出来的矩形的最大面积。
以上是柱状图的示例，其中每个柱子的宽度为 1，给定的高度为 [2,1,5,6,2,3]。
图中阴影部分为所能勾勒出的最大矩形面积，其面积为 10 个单位。
示例:
输入: [2,1,5,6,2,3]
输出: 10
思路
- 暴力枚举。
两个柱子间矩形的高由他们之间最矮的柱子决定。在枚举矩形的时候，首先是枚举底长[i:j+1]，然后在底长范围中找到最低高度min(heights[i:j+1])，底长和最低高度相乘计算面积。
时间复杂度O(n**3)，空间复杂度O(1)。
def largestRectangleArea(self, heights: List[int]) -> int:
if len(heights)== 0:
return 0
if len(heights) == 1:
return heights[0]
max_area = 0
for i in range(len(heights)):
for j in range(i, len(heights)):
sub = heights[i:j+1]
area = (j-i+1) * min(sub)
max_area = max(max_area, area)
return max_area
- 分治法。
以最小高度为中心，将区域分为3份，区间的最大面积为
max（
最小高度 * 区间长度，
最小高度左边最大面积，
最小高度右边最大面积
）
def largestRectangleArea(self, heights: List[int]) -> int:
def devide(left, right):
if right < left:
return 0
min_index = left
for i in range(left, right + 1):
if heights[i] < heights[min_index]:
min_index = i
return max((right-left+1)*heights[min_index], devide(left, min_index-1), devide(min_index+1, right))
if len(heights) == 0:
return 0
if len(heights) == 1:
return heights[0]
return devide(0, len(heights)-1)
以上两种方法，使用python均超时
- 栈
维护一个栈，初始化将 -1入栈。
遍历heights数组，如果heights[i] > heights[i-1]，即heights[i]大于栈顶元素，则下标i入栈；
如果heights[i]<heights[i-1]，开始将栈顶元素弹出，直到遇到栈顶元素小于heights[i];
每次弹出下标计算的面积为：
（栈顶元素的左边界永远是栈内它的下一个元素， 右边界是遇到的比它小的第一个元素）
以栈顶元素为高 * 右边界到左边界之间的矩形为宽
即： heights[stack[top]] x (i - stack[top - 1] -1)
当达到数组尾部时，将栈中剩余元素全部弹出栈，在弹出时计算面积的公式为：
heights[stack[top]] x (heights.length - stack[top-1] - 1)
def largestRectangleArea(self, heights: List[int]) -> int:
if len(heights) == 0:
return 0
if len(heights) == 1:
return heights[0]
stack = [-1]
max_area = 0
for i in range(len(heights)):
while stack[-1] != -1 and heights[i] < heights[stack[-1]]:
h = stack.pop()
area = heights[h] * (i - stack[-1] - 1)
max_area = max(max_area, area)
stack.append(i)
while stack[-1] != -1:
h = stack.pop()
area = heights[h] * (len(heights) - stack[-1] - 1)
max_area = max(max_area, area)
return max_area
