/*     * 84. Largest Rectangle in Histogram      * 2016-5-13 by Mingyang     * 这里并不需要两个stack，只需要一个stack，装的是递增序列的index     * 直到遇到一个递减的时候，弹出来，求一个一个的面积大小     * 不过注意的是最后如果以递增的序列结尾的话，还需要一个一个的求完     */    public int largestRectangleArea(int[] height) {        if (height == null || height.length == 0) {            return 0;        }         Stack
     
       stack = new Stack
      
       ();             int max = 0;        int i = 0;         while (i < height.length) {            //push index to stack when the current height is larger than the previous one            if (stack.isEmpty() || height[i] >= height[stack.peek()]) {                stack.push(i);                i++;            } else {            //calculate max value when the current height is less than the previous one                int p = stack.pop();                int h = height[p];                int w = stack.isEmpty() ? i : i - stack.peek() - 1;                max = Math.max(h * w, max);            }             }         while (!stack.isEmpty()) {            int p = stack.pop();            int h = height[p];            int w = stack.isEmpty() ? i : i - stack.peek() - 1;            max = Math.max(h * w, max);        }         return max;    }