C/C++教程

LeetCode 84. 柱状图中最大的矩形 Cheat

本文主要是介绍LeetCode 84. 柱状图中最大的矩形 Cheat，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

Tag: 单调栈

如何得到答案：
遍历每根柱子，找出每根对应最大的矩形，取最大值即可。
对于每根柱子我们查找这个柱子能形成的最大矩形。这个柱子的形成的矩形左（右）边界是左（右）边分别第一个比它小的柱子。

如何得到每个柱子能形成的最大矩形：

假设2的高度为h,3 4为h +1。
对于上图的2，我们穷举2能形成的最大矩形时，1和6分别是左边界和右边界。
其中的345是大于等于2的高度的，因此不会挡住2形成最大矩形。
345是等价的，对于2来说他们都只能取2的高度h，因此形成矩形面积为 h * 宽度。
高度同样为h的5形成的最大矩形和2的相同
单调栈满足栈内元素单调递增或者递减的性质。
利用（严格递增）单调增栈来计算当前入栈元素形成的最大矩形。栈中存放柱子下标
因为严格单调递增，对于栈中的柱子 左边界就是 就是元素底下的元素而右边界是第一个比它小的元素，需要注意矩形 宽度为 左边界和右边界之间的宽度 ：右边界 - 左边界 - 1

代码见题解

这篇关于LeetCode 84. 柱状图中最大的矩形 Cheat的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航