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
```