Leetcode84. 柱状图中最大的矩形(单调栈)

时间:2022-11-16 14:41:34

84. 柱状图中最大的矩形

前置

单调栈

做法

  • 连续区间组成的矩形,是看最短的那一块,求出每一块左边第一个小于其高度的位置,右边也同理,此块作为最短限制。需要两次单调栈

  • 单调栈维护递增区间,每次不满足弹出栈顶,顺便利用此栈顶和当前位置计算栈顶能覆盖的长度 用来计算。仅需一次单调栈