leetcode_699. 掉落的方块

https://leetcode-cn.com/problems/falling-squares/solution/cong-xian-duan-shu-dao-tu-lun-jian-mo-by-wotxdx/

线段树 https://cp-algorithms.com/data_structures/segment_tree.html

ZKW线段树 https://www.cnblogs.com/Judge/p/9514862.html

 初版16ms

namespace SegTree{
    // 描述方块以及高度
    class Node {
        public:
            //maxR作为最大边界
            int l, r, h, maxR;
            Node* left; 
            Node* right;
            Node(int l, int r, int h, int maxR) : l(l),r(r),h(h),maxR(maxR),left(NULL),right(NULL) {}
    };
    Node* insert(Node* root, int l, int r, int h) {
        if(root==NULL){
            Node* ret=new Node(l, r, h, r);
            return ret; }
        if(l<=root->l){
            root->left=insert(root->left,l,r,h);
        }else{
            root->right=insert(root->right,l,r,h);
        }
        //更新最大右边界
        root->maxR=max(r,root->maxR);
        return root;
    }
    int query(Node* root, int l, int r) {
        if(root==NULL||l>=root->maxR)return 0;
        //高度
        int curH=0;
        if(!(r<=root->l||l>=root->r)){
            curH=root->h;
        }
        //减枝
        curH = max(curH, query(root->left, l, r));
        //这里以左端为起点，如果新方块的右端在root->l的左边说明新方块就落在左边就不用查root的右边了
        if(r>root->l){
            curH = max(curH, query(root->right, l, r));    
        }
        return curH;
    }
}
class Solution {

public:
    vector<int> fallingSquares(vector<vector<int>>& positions) {
        // 创建返回值
        vector<int> res;
        // 根节点，默认为零
        SegTree::Node* root = NULL;
        // 目前最高的高度
        int maxH = 0;

        for (auto position : positions) {
            int l = position[0]; // 左横坐标
            int r = position[0] + position[1]; // 右横坐标
            int e = position[1]; // 边长
            int curH = SegTree::query(root, l, r); // 目前区间的最高的高度
            root = SegTree::insert(root, l, r, curH + e);
            maxH = max(maxH, curH + e);
            res.push_back(maxH);
        }
        return res;
    }
};

 改成使用引用12ms

namespace SegTree{
    // 描述方块以及高度
    class Node {
        public:
            //maxR作为最大边界
            int l, r, h, maxR;
            Node* left; 
            Node* right;
            Node(int l, int r, int h, int maxR) : l(l),r(r),h(h),maxR(maxR),left(NULL),right(NULL) {}
            Node(int l, int r, int h, int maxR,Node* left,Node* right) : l(l),r(r),h(h),maxR(maxR),left(left),right(right) {}
    };
    Node* insert(Node& root, int l, int r, int h,Node& default_node) {
        if(root.h==0){
            //Node* ret=new Node(l, r, h, r);
            return new Node(l, r, h, r,&default_node,&default_node); 
            }
        if(l<=root.l){
            root.left=insert(*root.left,l,r,h,default_node);
        }else{
            root.right=insert(*root.right,l,r,h,default_node);
        }
        //更新最大右边界
        root.maxR=max(r,root.maxR);
        return &root;
    }
    int query(Node& root, int l, int r) {
        if(root.h==0||l>=root.maxR)return 0;
        //高度
        int curH=0;
        if(!(r<=root.l||l>=root.r)){
            curH=root.h;
        }
        //减枝
        curH = max(curH, query(*root.left, l, r));
        //这里以左端为起点，如果新方块的右端在root.l的左边说明新方块就落在左边就不用查root的右边了
        if(r>root.l){
            curH = max(curH, query(*root.right, l, r));    
        }
        return curH;
    }
}
class Solution {

public:
    vector<int> fallingSquares(vector<vector<int>>& positions) {
        // 创建返回值
        vector<int> res;
        if(positions.size()==0){
            return res;
        }
        SegTree::Node* default_node=new SegTree::Node(0, 0, 0, 0);
        default_node->left=default_node;
        default_node->right=default_node;
        // 根节点，默认为零
        SegTree::Node* root = default_node;
        // 目前最高的高度
        int maxH = 0;
        for (auto position : positions) {
            int l = position[0]; // 左横坐标
            int r = position[0] + position[1]; // 右横坐标
            int e = position[1]; // 边长
            int curH = SegTree::query(*root, l, r); // 目前区间的最高的高度
            root = SegTree::insert(*root, l, r, curH + e,*default_node);
            maxH = max(maxH, curH + e);
            res.push_back(maxH);
        }
        return res;
    }
};