[Largest Rectangle in Histogram] AC Java solution, what is the running time, is it O(n)?


  • 0
    L

    According to the OJ, the code seems run very fast, but I am not certain about its running time, is it O(n)?

    public class Solution {
     
     public int largestRectangleArea(int[] height) {
            if (height.length ==0) return 0;
    
     //right[[i]  calculates the number of  consecutive bars from left side of the i-th bar   whose heights are       larger or equal to height[i],   including the i-th bar;
            int[] right = new int [height.length]; 
    
     //left[[i]  calculates the number of  consecutive bars from right side of the i-th bar   whose heights are larger or equal to height[i],   excluding the i-th bar;
            int[] left = new int [height.length];
    
     // record[i]  is just right[i] * height[i]
            int[] record = new int[height.length];
    
     // max is used to  store the maximal area;
            int max = 0;
    
     // build the arrays  int[] right and  int[] record  
            for (int i = 0; i < height.length; i++){
            	if (height[i] > max) max = height[i];
            }
            right[0] = 1;
            record[0] = height[0];
            left[height.length-1] = 0;
            
            for (int i = 1; i < height.length; i++){
                if (height[i-1] < height[i]) right[i] = 1;
                else{
                    int j = i - right[i-1] -1 ;
                        //  the following while loop  is the reason I am not sure the running time
                    while (j >= 0 && height[j] >= height[i]){
                        j-= right[j];
                    }// end while 
                    right[i] = i - j;	                		            
                }// end else
                record[i]= right[i] * height[i];
                
            }// end for
            
            int area = 0; 
      // build the array int[] left, and find the maximal area
            for (int i = height.length-2; i >= 0 ; i--){
                if (height[i+1] < height[i]) left[i] = 0;
                else{
                    int j = i + left[i+1] + 2 ;
                        //  the following while loop is the reason I am not sure the running time
                    while ( j < height.length && height[j] >= height[i]){
                        j+= left[j] + 1 ;
                    }// end while 
                    left[i] = j - i -1;
                     
                }// end else
                area = left[i] * height[i] + record[i];
                if ( area > max) max =  area;
                 
               
            }// end for
            if (record[height.length-1] > max) return record[height.length-1];
            return max;
            
            
             
        }// end largestRectangleArea
     }// end Solution

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.