柱状图中最大的矩形

Leetcode Link: 84. 柱状图中最大的矩形 - 力扣（LeetCode）

题目

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

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

解法一

思路： 这道题想的时候，往往是这样想的一个流程

1. 随便找一个柱子
2. 往左看往右看，看看包含这个柱子的所有矩形里面积最大的矩形

这样个想法太 naive，因为需要每次左走或者右走一个格子，然后考虑 这样走是大了还是小了？，对于每个柱子都这样，会很乱，同时很复杂

实际上，上面的问题可以总结成一句话

以每个柱子的高度为限制，包含这个柱子在内的这个高度的矩形面积是多少。

进一步，我们实际上就需要遍历每个柱子，并且找到左右第一个比这个柱子高度小的柱子之后，就可以计算我们在这个高度下，包含这个柱子的矩形面积。

下面是自己写的代码，细节很多，debug 了很久。大体思路是对的，但是有很多细节，很难一次性写对。

提前定义一个栈，遍历 height，提前往栈里添加一个哨兵 [(-float('inf'), -1)] 避免对于 0 位置的判断。注意这里添加的是列表，列表的元素是 tuple，其中保存了对应的高度和 idx

1. 如果当前位置 i 的高度 h 比栈顶列表中的最后一个高度低，则出栈，弹出的列表中的所有位置的对应面积=高*对应的底。一直重复弹出至栈顶的高比当前的高小或相等，执行2
2. 如果当前位置 i 的高度 h 比栈顶列表中的最后一个高度高，则入栈一个新的队列 [(h, i)]；如果相等，则将(h, i)append到到栈顶列表里，而不是入栈。（要处理好相等的问题）

最后，当遍历完 height 中，需要判断栈里是不是还有除了哨兵之外的东西，如果有，则一直弹出，计算对应位置的面积，其底的长度= len(height)-pop_element[i][-1][1]

细节注意

1. 高度相等时候，越大的 idx，在栈中对应的列表中越靠后，因此当我们遇到比这个高度大的柱子的时候，计算这个高度大的柱子对应的面积，要先从列表里取最大的 idx，即[-1]位置的，而不能偷懒直接取第一个等于这个高度的位置，即[0]。
2. 里面的索引很多，会很乱。

题解：

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        area = [0]*len(heights)
        stack = []  # 里面的样子[[(h1, i1), (h1, i4)], [(h2, i6)]]
        stack.append([(-float('inf'), -1)])  # 要 append 列表，可以保存相等的情况
        for i, h in enumerate(heights):
            if h > stack[-1][0][0]:  # 这里只关心栈顶的高度，因此取stack[-1][0][0]或者stack[-1][-1][0]都可以
                stack.append([(h, i)])
            else:
                while(h < stack[-1][0][0] and len(stack) > 1): # 只关心高度，同上
                    last = stack.pop()
                    for cur in last:
                        area[cur[1]] = heights[cur[1]]*(i-stack[-1][-1][1]-1) # 这里我们计算当前柱的面积，必需取在栈顶距离此柱子最近的柱子，因此必需取stack[-1][-1][0]，这里我开始就错了。
                if h == stack[-1][0][0]:
                    stack[-1].append((h, i))
                else:
                    stack.append([(h, i)])
        
        while(len(stack) > 1):
            cur = stack.pop()
            for x in cur:
                area[x[1]] = heights[x[1]]*(len(heights)-stack[-1][-1][1]-1) # 这里我们计算当前柱的面积，必需取在栈顶距离此柱子最近的柱子，因此必需取stack[-1][-1][0]
        
        return max(area)
 

可以参考题解的参考代码3 暴力解法、栈（单调栈、哨兵技巧） - 柱状图中最大的矩形 - 力扣（LeetCode） 该题解中，栈中并没有保存h，只保存了i。通过 height[stack[-1]]直接在height中找到对应高度。

启发和联系

同一题目最大矩形