Easy to understand O(nlogn) solution using Union-Find.


  • 2
    C

    This solution assumes you have implemented a QuickUnion union-find DS class, with logn complexity for Union operation.

    • Initially, enter all n indices into union-find, each with their own id.
    • Then create pairs of (height, index) for each histogram, put them into a vector, and sort the vector on height of histograms. We will use this vector as a stack (popping from highest height histograms).
    • while stack not empty
      • hist = element at the top, pop it
      • if this hist's left and/or right neighbor have height GREATER than this hist, then union with their sets. (This lets me know how many neighbors are to my left and right that have height >= mine. This is because of the order we pop from the stack, from largest to smallest).
      • Find the size of my cluster, from Union-Find DS.
      • candidate for max area is (sz of cluster)*(my height)
      • if this candidate is greater than previously recorded max area, update max area.

    And that's it, just return max area at the end. Here is the code:

    class Solution {
        class Hist {
        public:
            int ht;
            int index;
            Hist(int h, int i) : ht(h), index(i) {}
        };
    
    public:
        int largestRectangleArea(vector<int>& height) {
            if (height.size() == 0) return 0;
    
            vector<Hist> histograms;
            for (int i=0; i<height.size(); i++) {
                histograms.push_back(Hist(height[i], i));
            }
    
            std::sort(histograms.begin(), histograms.end(), [] (const Hist& lhs, const Hist& rhs) -> bool {
                return (lhs.ht < rhs.ht);
            });
    
            int max=0;
            QuickUnion uf(histograms.size());
            while (!histograms.empty()) {
                Hist hist = histograms.back(); histograms.pop_back();
                if (hist.index != 0 && hist.ht <= height[hist.index-1]) { //left neighbor
                    uf.Union(hist.index, hist.index-1);
                }
                if (hist.index != height.size()-1 && hist.ht <= height[hist.index+1]) { //right neighbor
                    uf.Union(hist.index, hist.index+1);
                }
                int clusterSz = uf.SizeSet(hist.index);
                if (max < (clusterSz * hist.ht)) {
                    max = clusterSz * hist.ht;
                }
            }
            return max;
        }
    };

  • 0
    A

    It would also be nice to post your QuickUnion class as there are many varying implementations of QuickUnion (eg. path compression)


Log in to reply
 

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