【单调栈】力扣85.最大矩形-代码解释

时间:2024-04-21 17:54:28

这里采用了 压缩数组 的方式进行计算(这个思想在 动态规划专题 中也练习过哦~)。

一维数组 h[map[0].length] 用来存放当前所在行的信息:以当前行为底,第 j 列的高度为多少。

注意:

  • 如果当前位置为 0 时,数组值归 0 。(当然不能以 0 为底啦)!
  • 否则,上一行此位置的值 + 1,就是当前此位置 1 的最大的高度。

得到了柱状图的高度大小之后,就划归成了计算柱状图的最大面积了,直接套用 上道题的代码 即可~

~ 点赞 ~ 关注 ~ 星标 ~ 不迷路 ~!!!

关注回复「ACM紫书」获取 ACM 算法书籍~

记得转发哦!