力扣刷题Day 20：柱状图中最大的矩形（84）

1.题目描述

2.思路

暴力解法会超出时间限制，但我自己又想不出来办法，所以最终摘抄学习了别人的代码，思路是：维护一个单调栈，高效地找出每个柱子左右两侧首个高度小于它的柱子，从而计算出以该柱子为高的矩形的最大面积，执行过程如下图：

3.代码（Python3）

class Solution:def largestRectangleArea(self, heights: List[int]) -> int:stack = []heights = [0] + heights + [0]answer = 0for i in range(len(heights)):while stack and heights[stack[-1]] > heights[i]:temp = stack.pop()answer = max(answer, (i - stack[-1] - 1) * heights[temp])stack.append(i)return answer

4.执行情况

5.感想

这道题好难啊！题解都看得我稀里糊涂的，只能跟着代码思路把执行流程走一遍，但是不知道这种思路到底是作者怎么想出来的。好挫败······

第二天我又回头看了一下，和每日温度（739）那道题其实是有相似之处的，我现在已经完全明白咯，总结如下：

单调栈的典型应用场景就是在一维数组中找第一个满足某种条件的数，比如“每日温度”（739）里的单调栈是用来存目前还没找到下一高温的天数、“柱状图中最大的矩形”（84）中的单调栈用来存目前还没找到最大矩形的柱子（作为矩形高）。