力扣刷题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.感想

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