84.柱状图中最大的矩形

思路： 这道题和接雨水很像，不过有两点差别：

1. 这道题需要找到一个位置前一个比他小的数和后一个比他小的数，而接雨水是找到前一个和后一个比他大的数。
2. 需要在原数组前后各补上0，防止忽略一些边缘的情况。

java">class Solution {public int largestRectangleArea(int[] heights) {Deque<Integer> stack=new LinkedList<>();int[] newHeights=new int[heights.length+2];newHeights[0]=0;newHeights[heights.length+1]=0;for(int i=0;i<heights.length;i++){newHeights[i+1]=heights[i];}stack.push(0);int res=0;for(int i=1;i<newHeights.length;i++){if(newHeights[i]>newHeights[stack.peek()]){stack.push(i);}else if (newHeights[i] == newHeights[stack.peek()]) {stack.pop(); // 这个可以加，可以不加，效果一样，思路不同stack.push(i);}else{while(!stack.isEmpty() && newHeights[i]<newHeights[stack.peek()]){int mid=stack.peek();stack.pop();int left=stack.peek();int right=i;int h=newHeights[mid];int w=right-left-1;res=Math.max(res,h*w);}stack.push(i);}}return res;}
}

时间复杂度O（n）
空间复杂度O（n）