A solution with 'Cartesian Tree'


  • 0
    F
     The stack method is subtle and concise. But I also find this problem can be elegantly solved using 'Cartesian Tree' .
    
    
    class Solution {
    public:
        ~Solution() { if(root) delete root; }
    
        int largestRectangleArea(vector<int>& height) {
            root = buildMinTree(height);
            return ComputeLargestRectangle(root, height, 0, height.size());
        }
        
    private:
        struct TreeNode {
            int index;
            TreeNode *left, *right;
            TreeNode(int _i): index(_i), left(nullptr), right(nullptr){}
            ~TreeNode() {
                if(left)   delete left;
                if(right)  delete right;
            }
        };
        TreeNode *root;
        
        TreeNode* buildMinTree(const vector<int> &height)
        {
            stack<TreeNode*> mystk;
            TreeNode *last = nullptr, *curNode;
            for(int i = 0; i < height.size(); ++i)
            {
                curNode = new TreeNode(i);
                while(!mystk.empty() && height[(last = mystk.top())->index] > height[i])
                    mystk.pop();
                if(mystk.empty())
                    curNode->left = last;
                else
                {
                    curNode->left = last->right;
                    last->right = curNode;
                }
                mystk.push(curNode);
            }
            while(mystk.size() > 1)
                mystk.pop();
            return mystk.empty()?nullptr : mystk.top();
        }
        
        int ComputeLargestRectangle(TreeNode* root, const vector<int> &height, int start, int end)
        {
            if(!root)
                return 0;
            return max(height[root->index]*(end - start), max(ComputeLargestRectangle(root->left, height, start, root->index), ComputeLargestRectangle(root->right, height, root->index+1, end)));
        }
    };

  • 0
    T

    Actually the construction of Cartesian tree is nearly the same as the process of the purely stack-based algorithm.


Log in to reply
 

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