84. 柱状图中最大的矩形

题目描述

给了一个数组表示柱子的高度，柱子的宽度是1,问能勾勒出的矩形的最大面积？

基本分析

1. 可能的最大矩形面积是咋算的？对某个位置i的高度h[i]来说，最大面积是向左找到最近的比他低的高度l[i], 向右找到最近的比他低的高度r[i], 宽度是r[i] - l[i]- 1
2. 什么结构可以做到？单调栈能保证在结构中索引递增，且只满足某种单调关系；借助这个关系可以实现找最近的大或者小的需求。
3. 栈弹出后之前的信息可能就没了，怎么能知道每个位置对应的信息？栈只是个工具，最终的信息另外开数组来存
4. 三叶的思路是咋样的？（1）定义了l和r数组，l初始化为-1，r初始化为n，表示默认不存在比h[i]值小的数组，这个时候宽度就是n。(2)以维护r数组为例，在枚举h[i]的时候，如果h[stk[-1]] > h[i], 表示在i的左边存在一个值，对这个值来说，i是最近的且小的右端点，r[cur] = i。这么做可以保证i是满足cur 维护左端点类似。(3)这个做法会存在覆盖问题吗？比如对[3, 2, 1, 4]而言，当遍历到索引2(值1)的时候，后栈中弹出1（值是2），r[1]=2; 然后继续弹出3，r[0]=1就错了?需要注意的是，栈中每个元素只会入栈和出栈一次。在枚举索引1的时候，就会stk中就会弹出索引0，r[0]=1; 后面在处理到1的时，栈中只会有[1]这个索引不会覆盖
5. 官解1的不同？(1)不是对当前i来找之前的cur，表示离cur最近的比h[cur]小的i；而是对当前的i找之前的最近的<h[i]的索引，这个索引。这样做有啥问题？不像i是存在的，这个索引可能不存在，这样就需要有
6. 官解2怎么做到一次遍历？（1）找左边的套路是一样的，只不过对弹出的cur和三叶的做法类似，前者是>关系，严格对，后者是>=关系，对于类似[1, 2, 2, 1]这种情况，r[1]的值是错误的；（2）但为什么ans不会错？对索引2的未位置来说，答案是对的，最终取最大的时候，保证不会错

单调栈

三叶做法

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        n = len(heights)
        l, r = [-1] * n, [n] *n
        stk = []
        for i in range(n):
            while stk and heights[stk[-1]] > heights[i]:
                # 每次从栈中弹出比h[i]大的索引
                cur = stk.pop()
                # cur位置右边最近的比他h小的索引是i
                r[cur] = i
            stk.append(i)
			
        stk = []
        for i in range(n-1, -1, -1):
            while stk and heights[stk[-1]] > heights[i]:
                cur = stk.pop()
                l[cur] = i
            stk.append(i)

        ans = 0
        for i in range(n):
            area = heights[i] *(r[i] - l[i] - 1)
            ans = max(ans, area)
        return ans

官解1

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        n = len(heights)
        l, r = [-1] * n, [n] * n

        stk = []
        for i in range(n):
            # 都不是i要找的值
            while stk and heights[stk[-1]] >= heights[i]:
                stk.pop()
            if stk:
                l[i] = stk[-1]
            stk.append(i)
        
        stk = []
        for i in range(n-1, -1, -1):
            while stk and heights[stk[-1]] >= heights[i]:
                stk.pop()
            if stk:
                r[i] = stk[-1]
            stk.append(i)
        
        ans = 0
        for i in range(n):
            h = heights[i]
            w = r[i] - l[i] - 1
            ans = max(ans, h * w)
        return ans

官解2 一次遍历

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        n = len(heights)
        l, r = [-1] * n, [n] * n
        stk = []

        for i in range(n):
            while stk and heights[stk[-1]] >= heights[i]:
                cur = stk.pop()
                # 相等的时候，只有最后一个是对的
                r[cur] = i
            if stk:
                l[i] = stk[-1]
            stk.append(i)
        
        ans = 0
        for i in range(n):
            h = heights[i]
            w = r[i] - l[i] - 1
            ans = max(ans, h * w)
        return ans

总结

1. 不同做法看待问题的角度不一样，可以遍历i的时候把弹出的元素当做索引处理和i的关系；也可以把弹完以后，处理i和stk[-1]的关系；后者更为直接
2. 正序遍历的时候，索引是递增的。三叶做法是栈顶严格>时候弹，这样i就是cur的一个边界；官解做法是判断栈顶>=的情况弹，最终弹完以后的h[栈顶]会严格<h[i]。前者维护的是一个高度单调上升的栈，允许=；后者是严格单调增，=的情况也会弹出去。