单调栈解决leetcode-84柱状图中最大的矩形

思路: 比如当前柱子的高度是h,这个问题的本质就是分别算出当前柱子左右两侧,第一个小于h柱子的位置,左侧leftMin如果比0小就是-1,右侧rightMin比索引大就是index+1·,最后当前柱子的最大面积就是(rightMin-leftMin-1)*h,然后比较每个柱子的最大柱子,得到最终结果。   首先最先想到的是暴力法,根据两层循环遍历,算出每个柱子的最大面积。   单调栈法: 首先补充下单调栈的概念: 从栈尾到栈顶递减就是单调递减栈; 从栈尾到栈懂递增就是单调递增栈。 单调栈解决leetcode-84柱状图中最大的矩形 单调递增栈,可以找到左右两边第一个比他小的元素; 单调递减栈,可以找到左右两边第一个比他大的元素。 对于每个元素,其有且仅有一次插入,最多出现一次删除,故其时间复杂度为O(n)。   当元素出栈时,说明这个新元素是出栈元素向后找第一个比其小的元素     用单调递增栈解决当前问题,因为要找出左右两侧第一个比他小的元素的位置。遍历到一个元素的时候,如果当前栈不为空,就比较栈顶元素和当前元素i的大小,如果i比栈顶小,那栈顶元素就是右侧第一个比i小的元素,弹出栈顶元素,最后栈为空或者当前元素大于栈顶元素就跳出循环;判断栈是否为空,为空说明当前元素左侧没有比他小的,不为空就是栈顶是右侧第一个比他小的元素。最后栈中还剩数据,说明这些元素的右侧没有比他小的。     对于栈里的元素来说,当前准备入栈的元素就是他们右侧,如果有元素弹出,当前准备入栈的元素就是弹出元素右侧第一个比他小的; 对于准备入栈的元素来说,栈里的元素就是他的左侧,如果在当前元素入栈的时候栈为空,说明左侧没有比他小的,如果栈不为空,栈里都是比他小的元素,那么栈顶就是右侧第一个比他小的元素。   一次遍历就可以拿到每个位置左右两侧第一个比他小元素的索引。     题目: 给定 n 个非负整数,用来表示柱状图中各个柱子的高度。每个柱子彼此相邻,且宽度为 1 。   求在该柱状图中,能够勾勒出来的矩形的最大面积。    解答: public class LargestRectangleArea_84 { public static int largestRectangleArea(int[] heights) { int n = heights.length; int[] left = new int[n]; int[] right = new int[n];   Deque<Integer> stack = new ArrayDeque<Integer>(); for(int i=0;i<heights.length;i++) { //单调递增栈,找出右边第一个小于当前元素的值 //把数组索引存在stack中,当栈不为空且当前栈顶的节点小于当前数组时候, //入栈的时候,如果栈为空,说明他的左侧没有比当前入栈位置要小的元素,左侧比他小的位置就是-1, //如果栈中有元素的时候,栈顶的数就是左侧第一个比他小的数 while(!stack.isEmpty()&&heights[stack.peek()]>heights[i]) { right[stack.pop()]=i; } //判断栈是否为空,为空说明当前元素左侧没有比他小的,不为空就是栈顶是右侧第一个比他小的元素。 left[i]=stack.isEmpty()?-1:stack.peek(); stack.push(i); } //栈中还剩数据,说明栈中数据右侧没有比他小的,全部填充为数组长度 while(!stack.isEmpty()) { right[stack.pop()]=heights.length; }   int max=0; for(int i=0;i<left.length;i++) { max=Math.max(max, (right[i]-left[i]-1)*heights[i]); }       return max; }   public static void main(String[] args) { int[] array= {6, 7, 5, 2, 4, 5, 9, 3}; largestRectangleArea(array); }   }

上一篇:NOIP提高组模拟赛7


下一篇:swap函数的例子