求柱状图中最大的矩形

问题:

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

方法一:暴力

# leetcode submit region begin(Prohibit modification and deletion)
class Solution(object):
    def largestRectangleArea(self, heights):
        """
        :type heights: List[int]
        :rtype: int
        """
        length = len(heights)
        max_area = 0
        for i in range(length):
            min_height = math.inf
            for j in range(i, length):
                min_height = min(min_height, heights[j])
                area = min_height * (j-i+1)
                max_area = max(area, max_area)
        return max_area
# leetcode submit region end(Prohibit modification and deletion)

方法二:优化,遍历每个柱子,左右扩展找满足条件的左柱和右柱

# leetcode submit region begin(Prohibit modification and deletion)
class Solution(object):
    def largestRectangleArea(self, heights):
        """
        :type heights: List[int]
        :rtype: int
        """
        length = len(heights)
        max_area = 0
        for i in range(length):
            current_height = heights[i]
            left = right = i
            while (left-1 >= 0 and heights[left-1] >= current_height):
                left -= 1
            while (right+1 < length and heights[right+1] >= current_height):
                right += 1
            max_area = max(max_area, (right-left+1) * current_height)
        return max_area
# leetcode submit region end(Prohibit modification and deletion)

 

上一篇:页面查询接口测试Swagger


下一篇:LeetCode #84. 柱状图中最大的矩形 题解 C/C++