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