My answer was accepted in 88ms, but i'm not sure about it's time complexity


  • 1
    L

    For every integer j between f[i] and i, we have height[j] >= height[i]. For every integer j between i and b[i], we have height[j] >= height[i]. And of course, among all possible integers, f[i] is the smallest one while b[i] is the largest one.
    I think the time complexity of this algorithm is O(n), but I'm not sure.

    int largestRectangleArea(vector<int> &height) {
        int n = height.size();
        
        if (n == 0) return 0;
        
        vector<int> f(n), b(n);
        
        f[0] = -1;
        for (int i = 1; i < n; ++ i) {
            f[i] = i-1;
            while (f[i] != -1 && height[f[i]] >= height[i]) {
                f[i] = f[f[i]];
            }
        }
        b[n-1] = n;
        for (int i = n-2; i > -1; -- i) {
            b[i] = i+1;
            while (b[i] != n && height[b[i]] >= height[i]) {
                b[i] = b[b[i]];
            }
        }
        
        int maxval = height[0];
        for (int i = 1; i < n; ++ i) {
            maxval = max(maxval, height[i]*(b[i]-f[i]-1));
        }
    
        return maxval;
    }

  • 0
    V

    O(n) time complexity as every bar is visited in constant number of times relative to input list size.


  • 0
    L

    Could you explain it in a clearer way? Suppose there exists a strictly non-decreasing subsequence from position i to j and height[j+1] < height[i], then it'll take at least O(j-i) of time to calculate f[j+1] since for each k between i+1 and j, f[k] = k-1. It takes O(1) time to caculate each f[k] (i+1 <= k <= j), though. I suppose the average visited times of each bar is 2, am I right?


  • 0
    V

    yes; as the average visited time for each is bar is constant relative to input size; program runs in O(n) time complexity


  • 0
    F

    I believe your algorithm is not O(n) since there are two while's in the for loop. However, it is not that worse to O(n^2) since f[i] or b[i] decrease / increase very fast to end the while. Maybe the exact complexity can be proved. I guess is something like O(nlogn)


Log in to reply
 

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