这里采用了 压缩数组 的方式进行计算(这个思想在 动态规划专题 中也练习过哦~)。
一维数组 h[map[0].length]
用来存放当前所在行的信息:以当前行为底,第 j
列的高度为多少。
注意:
- 如果当前位置为 0 时,数组值归 0 。(当然不能以 0 为底啦)!
- 否则,上一行此位置的值 + 1,就是当前此位置 1 的最大的高度。
得到了柱状图的高度大小之后,就划归成了计算柱状图的最大面积了,直接套用 上道题的代码 即可~
~ 点赞 ~ 关注 ~ 星标 ~ 不迷路 ~!!!
关注回复「ACM紫书」获取 ACM 算法书籍~
记得转发哦!