给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。
以上是柱状图的示例，其中每个柱子的宽度为 1，给定的高度为
[2,1,5,6,2,3]
。
图中阴影部分为所能勾勒出的最大矩形面积，其面积为
10
个单位。
示例:
输入: heights = [2,1,5,6,2,3]
输出: 10
暴力解法: 假设正确结果中包含heights[0]，则计算以heights[0]为开始的最大面积。后面以此类推，最终将以2，1，5，6，2，3为开始的最大面积比较，得出最大值
思想: 最大矩阵面积必定是以2，1，5，6，2，3其中一个为开头的， 我只要固定矩阵的开始位置，比较不同开始位置的最大值即可。
结果: 超时
class Solution:
def largestRectangleArea(self, heights):
"""
:type heights: List[int]
:rtype: int
"""
l = len(heights)
max_area = 0
for i in range(l):
height_min = 100000000000
for j in range(i, l):
height_min = min(height_min, heights[j])
max_area = max(max_area, height_min*(j-i+1))
return max_area
优化一:
矩阵的最大面积必定是以2，1，5，6，2，3其中一个为高的，
我只要比较以2为高的最大矩阵面积，
以1为高的最大矩阵面积，
以5为高的最大矩阵面积，
以6为高的最大矩阵面积，
以2为高的最大矩阵面积，
以3为高的最大矩阵面积
即可。 转换思想，暴力方法固定开始位置的思想，现在是固定高度。
设立left和right列表。 left[i] = k表示:
heights[k] < heights[i] ,
j = k+1,...., i 满足 heights[j] >= heights[i]
以heights = [2,1,5,6,2,3]
left = [-1,-1,1,2,1,4]
right =[1,6,4,4,6,6]
最后在遍历一遍heights
class Solution:
def largestRectangleArea(self, heights):
"""
:type heights: List[int]
:rtype: int
"""
# 优化过的
l = len(heights)
if l == 0:
return 0
if l == 1:
return heights[0] * 1
left = [0] * len(heights)
right = [0] * len(heights)
left[0] = -1
for i in range(1, l):
if heights[i] > heights[i-1]:
left[i] = i - 1
else:
# 优化的地方
j = left[i-1]
tmp = heights[i]
while (j >= 0 and heights[j] >= tmp) or j == -1:
if j == -1:
left[i] = -1
break
j = j - 1
left[i] = j
right[l-1] = l
max_area = 0
for i in range(l-2, -1,-1):
if heights[i] > heights[i+1]:
right[i] = i + 1
else:
j = right[i+1]
tmp = heights[i]
while (j <= l-1 and heights[j] >= tmp) or j == l:
if j == l:
right[i] = l
break
j = j + 1
right[i] = j
max_area = max(max_area, (right[i]-left[i]-1)*heights[i])
max_area = max(max_area, (right[l-1]-left[l-1]-1)*heights[l-1])
return max_area
方法三: 递增栈
目前不理解
class Solution:
def largestRectangleArea(self, heights):
"""
:type heights: List[int]
:rtype: int
"""
heights.append(0)
st, mx = [], 0
for i in range(len(heights)):
while st and heights[st[-1]] >= heights[i]:
c = st.pop()
mx = max(mx, heights[c]*(i-st[-1]-1 if st else i))
st.append(i)
return mx