Sharing my 16ms C++ solution


  • 0
    T
    class Solution {
    public:
        int largestRectangleArea(vector<int>& heights) {
            int n = heights.size();
            vector<int> left(n);
            vector<int> right(n);
            int i;
            
            for(i=0; i<n; i++)
            {
                left[i]=i-1;
                right[i]=i+1;
            }
            
            for(i=0; i<n; i++)
            {
                while(left[i]>=0 && heights[i]<=heights[left[i]])
                    left[i] = left[left[i]];
            }
            
            for(i=n-1; i>=0; i--)
            {
                while(right[i]<n && heights[i]<=heights[right[i]])
                    right[i] = right[right[i]];
            }
            
            int result = 0;
            for(i=0; i<n; i++)
                result = max(result, (right[i]-left[i]-1)*heights[i]);
                
            return result;
        }
    };

  • 0
    F

    Although the time consumption is low, but it is still O(n^2).


Log in to reply
 

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