【每日一题】7月24日题目精讲—小A的柱状图

题号 NC23619
名称 小A的柱状图
来源 牛客小白月赛13
戳我进入往期每日一题汇总贴~
往期每日一题二期题单



如果你在题库做题时遇到了喜欢的题目，欢迎推荐给邓老师~ 点击查看详情

题解

单调栈优化枚举的典型题
（先看特殊情况）如果是个递增的序列，那么每个小矩形如果要维持自己的高度，都只能向右延伸，而且能延伸到最右边，所以以每个小矩形为高度限制，计算面积即可。
如果原序列不递增，当h[i] > h[i+1]，i左边的矩形如果想要延伸到右边肯定是不需要i的高度的也就是说h[i]比h[i+1]大的那部分之后就都没有用了，我们把它高度变得和h[i]齐平就可以了。
所以用一个单调栈维护每个矩形的高度和宽度，当前矩形高于栈顶，进栈；否则，不断地取出栈顶计算被弹出矩形的宽度和并乘以他的高度计算有关的矩形大小知道栈顶小于当前矩形，然后把高度为当前矩形高度宽度为宽度和的矩形扔回栈内（相当于把当前矩形左边的比他高的全部削平成一个高度）。
最后记得把整个栈都弹出计算一下（里面保存了最后的一个高度递增的序列）。

活动奖励：

在牛客博客中写出题解，并回复地址
审核通过可获得（依据题目难度和题解的内容而定）

本道题目7月31日中午12：00之前写的题解有获得牛币资格~

.牛币兑换中心

牛客博客开通方式

1. 如何开通牛客博客：https://www.nowcoder.com/discuss/202952
2. 如何使用博客搬家功能：进入博客--->设置--->底部博客搬家
3. 如果你对牛客博客有任何意见或建议：牛客博客意见反馈专贴