【算法五十六】84. 柱状图中最大的矩形

84. 柱状图中最大的矩形 - 力扣LeetCode单调栈class Solution { public int largestRectangleArea(int[] heights) { //单调栈 int n heights.length; int[] newHeights new int[n2]; //加哨兵0第一个0是为了防止栈空最后一个0是弹出所有的数 for(int i 0;in;i){ newHeights[i1] heights[i]; } int maxArea 0; //存下标因为要算width需要用到下标 DequeInteger stack new ArrayDeque(); for(int i 0;in2;i){ while(!stack.isEmpty() newHeights[i]newHeights[stack.peek()]){ int mid stack.pop(); int height newHeights[mid]; int width i-stack.peek()-1; maxArea Math.max(maxArea,height*width); } stack.push(i); } return maxArea; } }时间复杂度O(N)空间复杂度O(N)