平面设计软件下载网站,收录软件最多的网站,wordpress 开发商城,西安比较好的软件公司84.柱状图中最大的矩形
题目要求#xff1a;给定 n 个非负整数#xff0c;用来表示柱状图中各个柱子的高度。每个柱子彼此相邻#xff0c;且宽度为 1 。
求在该柱状图中#xff0c;能够勾勒出来的矩形的最大面积。 思路
单调栈
本地单调栈的解法和接雨水的题目是遥相呼…84.柱状图中最大的矩形
题目要求给定 n 个非负整数用来表示柱状图中各个柱子的高度。每个柱子彼此相邻且宽度为 1 。
求在该柱状图中能够勾勒出来的矩形的最大面积。 思路
单调栈
本地单调栈的解法和接雨水的题目是遥相呼应的。
为什么这么说呢42. 接雨水 (opens new window)是找每个柱子左右两边第一个大于该柱子高度的柱子而本题是找每个柱子左右两边第一个小于该柱子的柱子。
这里就涉及到了单调栈很重要的性质就是单调栈里的顺序是从小到大还是从大到小。
在题解42. 接雨水 (opens new window)中我讲解了接雨水的单调栈从栈头元素从栈头弹出到栈底的顺序应该是从小到大的顺序。
那么因为本题是要找每个柱子左右两边第一个小于该柱子的柱子所以从栈头元素从栈头弹出到栈底的顺序应该是从大到小的顺序
我来举一个例子如图 只有栈里从大到小的顺序才能保证栈顶元素找到左右两边第一个小于栈顶元素的柱子。
所以本题单调栈的顺序正好与接雨水反过来。
此时大家应该可以发现其实就是栈顶和栈顶的下一个元素以及要入栈的三个元素组成了我们要求最大面积的高度和宽度
理解这一点对单调栈就掌握的比较到位了。
除了栈内元素顺序和接雨水不同剩下的逻辑就都差不多了在题解42. 接雨水 (opens new window)我已经对单调栈的各个方面做了详细讲解这里就不赘述了。
主要就是分析清楚如下三种情况
情况一当前遍历的元素heights[i]大于栈顶元素heights[st.top()]的情况情况二当前遍历的元素heights[i]等于栈顶元素heights[st.top()]的情况情况三当前遍历的元素heights[i]小于栈顶元素heights[st.top()]的情况
每一次入栈新元素时我是一直向左边比较比我小的柱子计算面积并且更新result的。这个思路好神奇我还是没有太想明白中间在while中一直在pop是怎么继续比较的。我个人认为一直在计算的是以每一个i为结尾right能够组成的最大矩形长度这样理解就对了。因为如果当前的i对应的值是2之前有56。即便2之后在出现6由于2存在的原因也无法组成以5、6为高度的矩形了所以2能够pop掉2之前所有比2大的st.top()。
class Solution {
public:int largestRectangleArea(vectorint heights) {int result 0;stackint st;heights.insert(heights.begin(), 0);heights.push_back(0);st.push(0);for (int i 1; i heights.size(); i) {if (heights[i] heights[st.top()]) {st.push(i);} else if (heights[i] heights[st.top()]) {st.pop();st.push(i);} else if (heights[i] heights[st.top()]) {while (!st.empty() heights[i] heights[st.top()]) {int mid st.top();st.pop();if (!st.empty()) {int left st.top();int right i;int w right - left - 1;int h heights[mid];result max(result, w * h);cout mid left right w h result endl;}}st.push(i);}}return result;}
};
细心的录友会发现我在 height数组上后都加了一个元素0 为什么这么做呢
首先来说末尾为什么要加元素0
如果数组本身就是升序的例如[2,4,6,8]那么入栈之后 都是单调递减一直都没有走 情况三 计算结果的哪一步所以最后输出的就是0了。 如图 那么结尾加一个0就会让栈里的所有元素走到情况三的逻辑。
开头为什么要加元素0
如果数组本身是降序的例如 [8,6,4,2]在 8 入栈后6 开始与8 进行比较此时我们得到 mid8rigt6但是得不到 left。
mid、leftright 都是对应版本一里的逻辑
因为 将 8 弹出之后栈里没有元素了那么为了避免空栈取值直接跳过了计算结果的逻辑。
之后又将6 加入栈此时8已经弹出了然后 就是 4 与 栈口元素 8 进行比较周而复始那么计算的最后结果resutl就是0。 如图所示 所以我们需要在 height数组前后各加一个元素0。
结束啦今天就是算法训练营的Day60
