O(n) C++ solution with comments


  • 0
    G
        int largestRectangleArea(vector<int>& H) {
            // stack to hold heights in the increasing order of active rectangles.
            // active rectangles are those that are opened but not closed yet.
            stack<int> s;
            int max_area = 0, i = 0;
            
            while (i < H.size()) {
                if (s.empty() || H[s.top()] <= H[i]) s.push(i++);
                else {
                    int tp = s.top();
                             s.pop();
                    // The rectangle with H[tp] as height must have started right after s.top().
                    max_area = max(max_area, H[tp] * (s.empty() ? i : (i - (s.top() + 1))));
                }
            }
            
            // Process the active rectangles.
            while (!s.empty()) {
                int tp = s.top();
                         s.pop();
                // The rectangle with H[tp] as height must have started right after s.top().
                max_area = max(max_area, H[tp] * (s.empty() ? i : (i - (s.top() + 1))));
            }
    
            return max_area;
        }
    

Log in to reply
 

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