leetcode84
给定 n 个非负整数,用来表示柱状图中各个柱子的高度。每个柱子彼此相邻,且宽度为 1 。
求在该柱状图中,能够勾勒出来的矩形的最大面积。

以上是柱状图的示例,其中每个柱子的宽度为 1,给定的高度为 [2,1,5,6,2,3]。

图中阴影部分为所能勾勒出的最大矩形面积,其面积为 10 个单位。
示例:
输入: [2,1,5,6,2,3]
输出: 10
链接:https://leetcode-cn.com/problems/largest-rectangle-in-histogram
class BaoSolution(object):
# 暴力法88%的数据通过,时间复杂度o(n^2)
def largestRectangleArea(self, heights):
"""
:type heights: List[int]
:rtype: int
"""
# 面积暂时存储每个高度的最大值,后边有比他大的再更新
area = max(heights)
size = len(heights)
# 初始base设为0
base = 0
# 暴力循环所有
for i in range(size-1):
# 以第i个为基准,后边的进行遍历
count = 1
# 如果当前的列值小于之前的列值,则不再重复循环,直接跳过
# 如果小于之前列值的再计算就全部是之前的计算的重复计算了
if heights[i] <= base:
continue
base = heights[i]
for j in range(i+1, size):
count += 1
if heights[j] < base:
# 遇到比基准小的值更新基准值
base = heights[j]
# 算出此时的面积
temp = base * count
# 如果比之前的面积大就更新
if temp > area:
area = temp
return area
class Solution(object):
# 借助递增栈的特性,时间复杂度o(n)
# 记录之前扫描过的状态,不重复扫描
def largestRectangleArea(self, heights):
"""
:type heights: List[int]
:rtype: int
"""
n = len(heights)
# 记录每个高度可以扩展到的最大矩形的左右边界
left, right = [0] * n, [n] * n
# 维护一个递增栈
stack = []
# 循环高度列表
for i in range(n):
# 当栈不空并且栈顶元素对应的高度值大于等于当前扫描的高度值时,可以求出栈底的高度对于的最大矩形面积
# 此时把他的右边界记录下来,就为当前扫描的高度值索引
while stack and heights[stack[-1]] >= heights[i]:
right[stack[-1]] = i
stack.pop()
# 如果不满足上边的条件,则记录左边界,入栈
left[i] = stack[-1] if stack else -1 # 如果栈不空,则左边界为栈顶,否则,左边界为-1
stack.append(i)
# 所有的高度对应最大矩形的左右边界都记录在了left和right中,此时计算最大面积即可
area = max([(right[i] - left[i] - 1) * heights[i] for i in range(n)]) if n > 0 else 0
return area
heights = list(map(int, input().split(',')))
solution = Solution()
res = solution.largestRectangleArea(heights)
print(res)
# 6,7,5,2,4,5,9,3