84. 柱状图中最大的矩形

Difficulty

Hard

动态规划

思路

遍历每根柱子，以当前柱子 i 的高度作为矩形的高，那么矩形的宽度边界即为向左找到第一个高度小于当前柱体 i 的柱体，向右找到第一个高度小于当前柱体 i 的柱体。

对于每个柱子我们都如上计算一遍以当前柱子作为高的矩形面积，最终比较出最大的矩形面积即可。

题解


class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        res = heights[0]
        stack = []
        heights = [0] + heights + [0]
        # 第一个和最后一个是手动新加上去的0，所以不用遍历
        for i in range(1, len(heights)-1):
            # 找左边第一个小于当前元素的下标
            for left in range(i-1,-1,-1):
                if heights[left] < heights[i]:
                    break
            # 找右边第一个小于当前元素的下标
            for right in range(i+1, len(heights), 1):
                if heights[right] < heights[i]:
                    break
            res = max(res, heights[i] * (right-left-1))

        return res

单调栈

类似上述动态规划，只是把寻找左右两边小于当前高度的过程用单调栈来处理实现了。维护一个递增栈，当当前元素小于栈顶时，那么

栈顶右边第一个小于栈顶的元素就是当前元素了，

栈顶左边第一个小于栈顶的元素就是当前栈顶弹出后的新栈顶

是以栈顶为的柱子的顶的。

题解


class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        res = heights[0]
        stack = []
				# 为了让栈在计算的时候不为空，且栈中的元素最后都能出去
        heights = [0] + heights + [0]
        for i in range(0, len(heights)):
            while stack and heights[i] < heights[stack[-1]]:
								# 栈顶的只要小于当前高度，直接推出去，直到栈继续为递增趋势
                preHeight = heights[stack.pop()]
								# 此处计算宽度，不能只计算栈顶到当前元素的宽度，
								# 还得把之前的但是又高于栈顶（只是在之前伦次中被pop掉的）宽度给计算上
 
                width = i - stack[-1] - 1
                res = max(res, preHeight*width)
            stack.append(i)

        return res