My 16ms C++ O(n) code without a stack


  • 7
    B

    Basically, I find the range (left[i], right[i]) within which the height of every element is at least height[i]. For each i, there is a rectangular with area height[i] * (right[i]-left[i]+1), and the largest area must be one of them. Then run all i to find the largest area. Please notice it takes O(n) time to fill left[i] and right[i] if we use DP. We can use amortization analysis to find this out. If you think about the worst case for a certain i, if it takes k steps in the while loop to get left[i]. Then it means there are k indices (for each j update below) which only take 1 step each in the loop to find left item for these indices. Then the average number of steps of these k+1 indices is const. So it takes O(n) to fill left and right arrays.

    class Solution {
    public:
        int largestRectangleArea(vector<int>& height) {
            int N=height.size(), i, j, l, r, area=0, temp;
            if(N==0) return 0;
            vector<int> left(N), right(N);
            left[0]=0;  //fill left[i] in the for loop
            for(i=1; i<N; ++i){
                l=i;
                j=i-1;
                while(j>=0&&height[j]>=height[i]){   // amortization shows const steps for this loop
                    if(height[j]==height[i]){
                        l=left[j];
                        break;
                    }
                    l=left[j];
                    j=left[j]-1;
                }
                left[i]=l;
            }
            right[N-1]=N-1;  //fill right[i] in the for loop
            for(i=N-2; i>=0; --i){
                r=i;
                j=i+1;
                while(j<N && height[j]>=height[i]){ 
                    if(height[j]==height[i]){
                        r=right[j];
                        break;
                    }
                    r=right[j];
                    j=right[j]+1;
                }
                right[i]=r;
            }
            for(i=0; i<N; ++i){
                temp=height[i]*(right[i]-left[i]+1);
                if(temp>area) area = temp;
            }
            return area;
        }
    };

  • 0
    A

    what is the time complexity? is it O(N^2)?


  • 0
    B

    It is O(n^2). Consider the worst case growing from small to big, the number in the middle is INT_MAX -1, then the other half decreases from big to small. It is o(n/2) + o(n/2)*o(n/2) ~ O(n^2)


Log in to reply
 

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