不忘初心,
牢记使命。

leetcode84-最大矩形面积

2021-05-11 大聪明 0评论 134 0喜欢

leetcode84

给定 n 个非负整数,用来表示柱状图中各个柱子的高度。每个柱子彼此相邻,且宽度为 1 。

求在该柱状图中,能够勾勒出来的矩形的最大面积。

img

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

img

图中阴影部分为所能勾勒出的最大矩形面积,其面积为 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

发表评论 取消回复

电子邮件地址不会被公开。

请输入正确格式的qq邮箱
请输入以http或https开头的URL,格式如:https://libo_sober.top