day63--单调栈3

本文主要是介绍day63--单调栈3，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

第一题：柱状图中最大的矩形

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。

 直接单调栈：

接雨水利用的是3个柱子形成一个凹槽，类似于213这样的形状，在1里面蓄水

而本题找的是每个柱子左右两边第一个小于该柱子的柱子

也就是利用三个柱子形成132这样的形状，凸状态然后求得面积

• 情况一：当前遍历的元素heights[i]大于栈顶元素heights[st.top()]的情况
• 情况二：当前遍历的元素heights[i]等于栈顶元素heights[st.top()]的情况
• 情况三：当前遍历的元素heights[i]小于栈顶元素heights[st.top()]的情况

先让栈按照从栈底到栈顶从小到大的顺序排列，如果出现了当前元素小于栈顶元素的时候，如状态132的凸字形，，，left为栈顶元素，right为当前元素，求得矩形的宽，然后高就是栈顶元素，最后求result=Max（result,w*h）;

2个月的学习完结，，，撒花✿✿ヽ(°▽°)ノ✿！！！

这篇关于day63--单调栈3的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---