solution alg problem

largest-area-of-histogram.cpp

template <class T>
class Links{
    public:
    list<T*> childs;
    T *parent;
};

class Node{
    public:
    Links<Node> rights;
    Links<Node> lefts;
    
    int height, leftWidth, rightWidth;
    // int index;
    Node() 
    { 
        height = 0; 
        // depth to left
        leftWidth = 0; 

        // depth to right
        rightWidth = 0; 
    }

    void setDepth(int depth, bool rightDirection){
        if (rightDirection){
            this->rightWidth = depth;
        }else{
            this->leftWidth = depth;
        }
    }

    int getDepth(int depth, bool rightDirection){
        if (rightDirection){
            return this->rightWidth;
        }else{
            return this->leftWidth;
        }
    }

    list<Node*>& forwards(bool rightDirection){
        return rightDirection ? this->rights.childs : this->lefts.childs;
    }

    Node* backward(bool rightDirection){
        return rightDirection ? this->rights.parent : this->lefts.parent;
    }
    /*
    * @return {new cursor}
    */
    Node* connect(Node* next, bool rightDirection){
        Node* cursor = this;
        while (cursor->height > next->height){
            cursor = cursor->backward(rightDirection);
        }
        cursor->forwards(rightDirection).push_back(next);
        if (rightDirection){
            next->rights.parent = cursor;
        }else{
            next->lefts.parent = cursor;
        }
        
        // // conditional which detect leaf
        // if (this != cursor){
        //     // it means that this is leaf
        //     this->setDepth(1, rightDirection);
        // }
        return next;
    }

    int calculateWidth(bool rightDirection){
        int &width = rightDirection ? this->rightWidth : this->leftWidth;
        if (width == 0){
            int sum = 0;
            for(auto n : this->forwards(rightDirection) ){
                sum += n->calculateWidth(rightDirection);
            }
            width = sum + 1;
        }
        return width;
    }

    int calcArea(){
        return this->height * (this->rightWidth + this->leftWidth - 1);
    }
};

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        Node rightRoot, leftRoot, *cur;
        cur = &leftRoot;
        vector<Node*> order;

        bool rightDirection = true;
        // int index = 0;
        for(int h : heights){
            Node* n = new Node;
            n->height = h;
            // n->index = index++;
            order.push_back(n);

            cur = cur->connect(n, rightDirection);
        }
        leftRoot.calculateWidth(rightDirection);
        
        rightDirection = false;
        cur = &rightRoot;
        for (vector<Node*>::reverse_iterator i = order.rbegin();i != order.rend(); ++i ) {
            Node* n = *i;

            cur = cur->connect(n, rightDirection);
        }
        rightRoot.calculateWidth(rightDirection);
        
        int maxA = 0;
        for(auto n : order){
            int area = n->calcArea();
            // cout<< n->leftWidth << " " << n->rightWidth << endl;
            if (area > maxA) {
                maxA = area;
            }
        }

        // for(auto n: order){
        //     cout << n->index << ":" ;
        //     for(auto child : n->rights.childs){
        //         cout << " " << child->index;
        //     }
        //     cout << endl;
        // }
        return maxA;
    }
};