Leetcode解题-Largest Rectangle in Histogram

发表于   |   分类于   |  

描述

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.

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

histogram-area
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.

分析

时间O(n^2)的算法很容易想，每个位置上向两边扩散就可以。不过还可以更好：利用一个栈，栈内维护递增的序列，遇到破坏递增的元素就持续出栈（这时栈顶元素能围成多大的矩形已经可以计算），直到当前元素大于栈顶，继续入栈。详细分析可参考这篇文章。

注意if not ss or height[i] > height[ss[-1]]: 中的判断>还是>=不影响正确性，想想为什么。

代码

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution(object):
    def largestRectangleArea(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        ss = []
        max_area = 0
        height.append(0)
        n = len(height)
        i = 0
        while i < n:
            if not ss or height[i] > height[ss[-1]]:
                ss.append(i)
                i += 1
            else:
                idx = ss.pop()
                w = i if not ss else i - 1 - ss[-1]
                max_area = max(max_area, height[idx] * w)
        return max_area

热评文章