Largest Rectangle in Histogram

vvpvvp 发布于2019-07-24 17:33 / 2098人阅读

摘要：而最大的矩形一定满足两个边界的高度小于该矩形的高度这个条件如果不满足的话，边界也可以被添加进来计算而不破坏矩形的形状，此时不为最大，因此找出所有这样的矩形就一定可以在其中找出面积最大的矩形。

Problem

Given n non-negative integers representing the histogram"s bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].

The largest rectangle is shown in the shaded area, which has area = 10 unit.

For example,
Given height = [2,1,5,6,2,3],
return 10.

Solution

暴力穷举法

最简单的自然是暴力法，即穷举左端坐标和右端坐标，计算两个坐标之间矩形的最大面积，再从所有的面积中得出最大的即为解。但是该方法至少需要两个for循环来遍历每一种左右端的组合，时间复杂度为O($n^2$)。以下是该方法的代码，解是对的，但在leetcode上会超时。

class Solution:
    # @param height, a list of integer
    # @return an integer
    def largestRectangleArea(self, height):
        length = len(height)
        max_area = -1
        for i in range(length):
            for j in range(i + 1, length):
                h = min(height[i: j])
                area = h * (j - i)
                if max_area < area:
                    max_area = area
        return max_area

利用栈减小时间复杂度

可以考虑，计算一个矩形的面积时，比如图

中的斜线部分，其两侧的高度一定是低于矩形所在的矩形条的高度的，因此可以通过维护一个栈来得出左端左边及右端坐标和矩形的高度，每一个矩形条只进栈一次，这样时间复杂度为O(n)。
1. 算法从左向右遍历每个矩形，以当前遍历的位置为右端坐标，如果栈为空或者当前矩形不低于栈顶的矩形，则将当前的位置坐标压栈，因为此时的坐标一定不是右边界（指要计算的面积右边的一个矩形条，不包含在要计算的面积中），例如图中，加入当前坐标为3，高度为6，栈顶坐标的高度为5，那么当前矩形条不可能作为右边界，将其压栈。
2. 如果当前位置的矩形低于栈顶的矩形条，那么当前位置可以作为一个矩形的边界，则从这个位置开始向左遍历，对每个高度大于右边界的矩形条作为左边界计算一次面积，直到高度小于右边界或栈为空。
3. 在遍历过一遍之后，如果栈不为空，则以栈中的每个坐标作为左边界计算一次面积，结合步骤2得出最大面积。
Accepted code如下：

class Solution:
    # @param height, a list of integer
    # @return an integer
    def largestRectangleArea(self, height):
        max_area = 0
        i = 0
        n = len(height)
        stack = []
        while i < n:
            if len(stack) == 0 or height[i] >= height[stack[-1]]:
                stack.append(i)
                i += 1
            else:
                top = stack.pop()
                area_with_top = height[top] * (i if len(stack) == 0 else i - stack[-1] - 1)
                if max_area < area_with_top:
                    max_area = area_with_top

        while len(stack) != 0:
            top = stack.pop()
            area_with_top = height[top] * (i if len(stack) == 0 else i - stack[-1] - 1)
            if max_area < area_with_top:
                max_area = area_with_top

        return max_area

这个方法并不是提供一个准确的找出最大的矩形的算法，而是通过试验那些“可能”成为最大的矩形的面积，再从其中找出最大的。而最大的矩形一定满足两个边界的高度小于该矩形的高度这个条件（如果不满足的话，边界也可以被添加进来计算而不破坏矩形的形状，此时不为最大），因此找出所有这样的矩形就一定可以在其中找出面积最大的矩形。

云服务器 GPU云服务器 HISTOGRAM Largest Rectangle rectangle图形删除

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/37307.html

[LeetCode] 84. Largest Rectangle in Histogram

Problem Given n non-negative integers representing the histograms bar height where the width of each bar is 1, find the area of largest rectangle in the histogram. showImg(https://segmentfault.com/img...

BaronZhang 2019-08-16 14:25 评论0 收藏0
[Leetcode] Largest Rectangle (in Histogram) 最大矩形

摘要：以此类推，如果一直到栈为空时，说明刚出来的竖条之前的所有竖条都比它自己高，不然不可能栈为空，那我们以左边全部的宽度作为长方形的宽度。 Largest Rectangle in Histogram Given n non-negative integers representing the histograms bar height where the width of each bar...

邹强 2019-08-14 12:24 评论0 收藏0
[LintCode] Largest Rectangle in Histogram

摘要：只要出现当前右边界高度小于等于栈顶元素高度的情况，就取出栈顶元素当前遍历过最高的并对这个元素进行取最大矩形的运算。 Problem Given n non-negative integers representing the histograms bar height where the width of each bar is 1, find the area of largest ...

alighters 2019-08-14 15:27 评论0 收藏0
leetcode84. Largest Rectangle in Histogram

摘要：题目要求即找到图中可以组合而成的面积最大的矩形。从而我们可以知道该矩形在水平方向上的最大扩展程度。也就是说，栈中数据记录了最远左侧下标，而当前的矩形则是最远右侧下标。当我们不采用数据结构时，寻找和计算的过程需要的时间复杂度。题目要求 Given n non-negative integers representing the histograms bar height where t...

Harpsichord1207 2019-08-15 10:55 评论0 收藏0
84. Largest Rectangle in Histogram

摘要：要求一个矩形的面积，要知道高和宽。如果每次确定高度为然后调用一个找到左右边界，即不小于的最左和最右。这是一个明显的算法，每次扫描都会重走整个。一个递增序列这种，我们知道可以够成的矩形是会不断增大的。递增序列预处理，递减的时候计算。 showImg(https://segmentfault.com/img/bVoQel); For example, Given heights = [2,...

melody_lql 2019-08-14 18:01 评论0 收藏0