Largest Rectangle in Histogram (LeetCode Array)

Question:  Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram. (full problem with examples please refer to Leetcode website).

Idea: Stack. Scan the array from left to right. When the integers in the array are monotonically increasing, the minimum value of the height does not change, but the width increases. In this case, there is no need to update the result unless reaching the end of the array. 

However, the integers in the array may not increase monotonically. Whenever a decrease happens (e.g. at position "k"), the minimum height may change. Now we compute the max area before k and pop the values bigger than height[k] to make height[k] the new minimum height. Then repeat doing that until the end of the array. Since we only update result when a decrease happens, to simplify the implementation, we can consider the right boundary of the array is a new minimum (e.g. -1), to avoid to write extra code on handling the boundary cases.

Time: O(n) Space: O(1)

Code:

 public class Solution {  
   public int largestRectangleArea(int[] height) {  
     if(height==null||height.length==0)  
       return 0;  
     Stack<Integer> indexStack=new Stack<Integer>();  
     int result=0;  
     for(int i=0;i<=height.length;i++)  
     {  
       int cur=(i==height.length)?-1:height[i];  
       while(!indexStack.isEmpty()&&height[indexStack.peek()]>=cur)  
       {  
         int h=height[indexStack.pop()];  
         int w=indexStack.isEmpty()?i:i-1-indexStack.peek();  
         result=Math.max(result,h*w);  
       }  
       indexStack.push(i);  
     }  
     return result;  
   }  
 }