Leetcode 84. 柱状图中最大的矩形 Largest Rectangle in Histogram

目录

1. 会超时的方法：
   1. 双重循环
   2. 分治算法
2. 正确解法
3. 超时代码
   1. 超时代码一 双重循环
   2. 超时代码一 分治

https://leetcode-cn.com/problems/largest-rectangle-in-histogram/

会超时的方法：

双重循环

最简单的思路，时间复杂度 O（n^2) 会超时（最后附超时代码）

分治算法

先找到当前数组中最小元素。

那么答案将在一下三种情况中：

1. 包含最小元素，那么高度是最小元素高度，长度是整个区间
2. 不包含最小元素，且在最下元素左边 （递归左半区间）
3. 不包含最小元素，且在最下元素有边 （递归右半区间）

这个方法的平均时间复杂度是 O（nlogn）

但是最坏情况时间复杂度仍是 O（n^2) 也会超时（最后附超时代码）

正确解法

从前向后遍历，过程中维护一个递增的栈。

如果下一个大于栈顶元素，就直接入栈。

如果小于，就把栈里大的元素都弹出来，并且计算高度是弹出的元素高度，宽度是当前元素到栈顶元素之间。

为什么可以以弹出元素高度为高度，当前位置和栈顶元素位置间的距离为宽度呢？因为栈是递增的，比弹出元素高度低的元素一定都在栈里，栈顶一定是离这个元素最近的一个（高度小于该元素的元素）换句话就是它们之间的元素高度都大于该元素。

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        hs = [0] + heights + [0]
        s = []
        ans = 0
        for i, h in enumerate(hs):
            while s and hs[s[-1]] > h:
                j = s.pop()
                ans = max(ans, hs[j] * (i-s[-1]-1))
            s.append(i)
        return ans

超时代码

超时代码一 双重循环

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        maxa = 0
        for i in range(len(heights)):
            minh = heights[i]
            for j in range(i, len(heights)):
                minh = min(minh, heights[j])
                maxa = max(maxa, minh * (j-i+1))
        return maxa

超时代码一 分治

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        def solve(l, r, d):
            if l >= r: return 0
            if l == r-1: return heights[l]
            min_i = l
            min_h = heights[l]
            for i, h in enumerate(heights[1+l:r]):
                if h < min_h:
                    min_h = h
                    min_i = i+l+1
            return max(min_h * (r - l), solve(l, min_i, d+1), solve(min_i+1, r, d+1))
        return solve(0, len(heights), 0)

参考