week8 stack 2

// Given n non-negative integers representing the histogram's bar height.
//The width of each bar is 1. calculate the area of largest rectangle in the histogram.

public int largestRectangleArea(int[] array){
  if (array == null || array.length == 0)
    return -1;
  Deque<Integer> stack = new ArrayDeque<Integer>(); //sotre the index
  int max = 0;
  for (int i = 0; i <= array.length; i++){
    int curVal = i == array.length ? 0 : array[i]; // Set curVal to the minimum value to guarantee the last element to be put into stack
   //1.Check whether curVal should be put into stack by comparing to peek
   while(!stack.isEmpty() && array[stack.peekLast()] >= curVal){
     int height = arry[stack.pollLast()];
     //Find left and right boundary from current rectabgle
     int leftBound = stack.isEmpty() ? 0 : stack.peekLast() + 1;
     int rightBound = i;
     max = Math.max(max, height*(rightBound -leftBound));
   }
   //2. Push the element into the stack
   stack.offerLast(i);
   }
   return max;
   }