📝【LeetCode】84 柱状图中最大的矩形

[imageslr]

https://imageslr.github.io/2020/02/02/leetcode-84.html

这道题是 LeetCode 84 题。

[zyksir]

优化解法4要怎么做到 O(n)呢？我想到的代码是这样子的

j = i - 1
while height[j] > height[i]:
    j = dp[j]

[imageslr]

@zyksir 因为我们要找到一个位置左、右第一个比它矮的柱子，所以需要从左往右、从右往左分别算一次。你这个公式是从左往右算，再结合一个从右往左算就可以了。

可以看看 42 题 - 接雨水的解法四，就是从左往右、从右往左算了两次左边、右边最高的柱子。