84. 柱状图中最大的矩形

题目地址(84. 柱状图中最大的矩形)

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

题目描述

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

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

前置知识

公司

• 暂无

思路

• 朴素的思路：枚举每一根柱子，然后向两边扩展，使得扩展到的柱子的高度均不小于h。也就是找到左右两个边界，也即左右两侧最近的高度小于h的柱子，这样两根柱子之间的所有柱子高度均不小于h。
• 那么怎么找左右边界？使用单调栈即可
  1）栈中存放了j值。从栈底到栈顶，j的值严格单调递增，同时对应的高度值也严格单调递增；
  2）当我们枚举到第 i 根柱子时，我们从栈顶不断地移除height[j] ≥ height[i] 的 j 值。在移除完毕后，栈顶的 j 值就一定满足height[j] < height[i]，此时 j 就是 i 左侧且最近的小于其高度的柱子。
  3）我们再将 i 放入栈顶。
• 优化：只遍历一次就能确定答案
  对位置i进行入栈时，确定了它的左边界。
  对位置i进行出栈时，可以确定它的有边界。当i被弹出栈是，说明此时遍历到的位置j的高度小于等于height[i]，并且在i与j之间没有其他高度小于等于height[i]的柱子。如果有的话，则在遍历那个位置的时候，i应该已经被弹出栈了。所以，j就是位置i的右边界。、
• 因此，一个非常重要的结论显而易见：i的左边界就是栈中的下一位，i的右边界，就是当i被弹出时遍历到的位置。

关键点

代码

• 语言支持：Go

Go Code:

func largestRectangleArea(heights []int) int {
    if len(heights) == 0 {
        return 0
    }
    if len(heights) == 1 {
        return heights[0]
    }
    stack  := []int{-1}
    n := len(heights)
    res := 0
    for i := 0; i < n; i++ {
        for len(stack) > 1 && (heights[i] <  heights[stack[len(stack) - 1]]) {
            area := (i - stack[len(stack) - 2] - 1) * heights[stack[len(stack) - 1]]
            stack = stack[:len(stack) - 1]
            if area > res {
                res = area
            }
        }
        stack = append(stack, i)
    }

    for len(stack) > 1 {
        area := (n - stack[len(stack) - 2] - 1) * heights[stack[len(stack) - 1]]
        stack = stack[:len(stack) - 1]
        if area > res {
            res = area
        }      
    }

    return res
}

更简单的写法，在原数组中加一个0，就可以去掉最后边界情况的循环，因为0比任何正数都小：

func largestRectangleArea(heights []int) int {
    if len(heights) == 0 {
        return 0
    }
    if len(heights) == 1 {
        return heights[0]
    }
    stack  := []int{-1}
    heights = append(heights, 0)
    n := len(heights)
    res := 0
    for i := 0; i < n; i++ {
        for len(stack) > 1 && (heights[i] <  heights[stack[len(stack) - 1]]) {
            area := (i - stack[len(stack) - 2] - 1) * heights[stack[len(stack) - 1]]
            stack = stack[:len(stack) - 1]
            if area > res {
                res = area
            }
        }
        stack = append(stack, i)
    }

    return res
}

复杂度分析

令 n 为数组长度。

• 时间复杂度：
• 空间复杂度：