第十章 单调栈part03

有了之前单调栈的铺垫，这道题目就不难了。 

•  84.柱状图中最大的矩形

  class Solution {int largestRectangleArea(int[] heights) {Stack<Integer> st = new Stack<Integer>();// 数组扩容，在头和尾各加入一个元素int [] newHeights = new int[heights.length + 2];newHeights[0] = 0;newHeights[newHeights.length - 1] = 0;for (int index = 0; index < heights.length; index++){newHeights[index + 1] = heights[index];}heights = newHeights;st.push(0);int result = 0;// 第一个元素已经入栈，从下标1开始for (int i = 1; i < heights.length; i++) {// 注意heights[i] 是和heights[st.top()] 比较 ，st.top()是下标if (heights[i] > heights[st.peek()]) {st.push(i);} else if (heights[i] == heights[st.peek()]) {st.pop(); // 这个可以加，可以不加，效果一样，思路不同st.push(i);} else {while (heights[i] < heights[st.peek()]) { // 注意是whileint mid = st.peek();st.pop();int left = st.peek();int right = i;int w = right - left - 1;int h = heights[mid];result = Math.max(result, w * h);}st.push(i);}}return result;}
  }

  思路：该题和接雨水类似，要求左面和右面较小的值，然后相减求出宽度，然后乘以h，利用单调栈求左右较小的值。注意要在数组前后加0，确保数组前后的数左右都能有比i小的值。