A solution with 'Cartesian Tree'

• `````` 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)));
}
};``````

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

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