企业网站推广的名词解释,百度网站建设公司,摄影网页设计模板,建设通会员多少钱一个年84. 柱状图中最大的矩形给定 n 个非负整数#xff0c;用来表示柱状图中各个柱子的高度。每个柱子彼此相邻#xff0c;且宽度为 1 。求在该柱状图中#xff0c;能够勾勒出来的矩形的最大面积。以上是柱状图的示例#xff0c;其中每个柱子的宽度为 1#xff0c;给定的高度为…84. 柱状图中最大的矩形给定 n 个非负整数用来表示柱状图中各个柱子的高度。每个柱子彼此相邻且宽度为 1 。求在该柱状图中能够勾勒出来的矩形的最大面积。以上是柱状图的示例其中每个柱子的宽度为 1给定的高度为 [2,1,5,6,2,3]。图中阴影部分为所能勾勒出的最大矩形面积其面积为 10 个单位。示例:输入: [2,1,5,6,2,3]输出: 10class Solution {/*** 利用单调栈 求解总体思路是 以柱子i高度为矩形高度时所能形成最大面积(利用性质找出第i个柱子向左边和右边遍历时第一个比它低的柱子)* 单调栈定义只存高度递增的柱子* 性质* 出栈时* 那么如果单调栈为空了说明没有比这个柱子更低的了(矩形宽度为这根柱子的序号左边沿为0)* 如果单调栈不为空说明栈里面的柱子高度都小那么左边沿为栈顶柱子的序号** 矩形右边沿为i 因为你出栈 就说明你比别人低了这已经是你能达到的面积极限了.出栈记录面积* **/public static int largestRectangleArea(int[] heights) {int heightn[] new int[heights.length1];for (int i 0; i heights.length; i) {heightn[i] heights[i];}heightn[heights.length] 0; //最后增加个高度为0 的柱子以便吧单调栈里面的都弹出去。Deque stack new ArrayDeque(); //存储序号int maxS0;for (int i 0; i heightn.length;i) {while (!stack.isEmpty() heightn[i]int tempstack.pop();//这里是递减数列得长度maxS Math.max(maxS,( ( stack.isEmpty()?i:(i-stack.peek()-1) )*heights[temp] ));}stack.push(i); //入栈}return maxS;}}
