LeetCode 699. Falling Squares

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    vector<int> fallingSquares(vector<vector<int>>& positions) {
        int n = positions.size(), i = 0;
        vector<int> ans(n, 0);
        for (auto &p : positions) {
            int l = p[0], h = p[1], r = l + h - 1;
            ans[i] = h;
            for (int j = 0; j < i; ++j)
                if (r >= positions[j][0] && l <= (positions[j][0] + positions[j][1] - 1))
                    ans[i] = max(ans[i], ans[j] + h);
            ++i;
        }
        for(i = 1; i < n; ++i)
            ans[i] = max(ans[i], ans[i - 1]);
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
class Solution {
public:
    const int N = 1e9;
    struct Node {
        int val, add;
        Node *ls, *rs;
    };
    Node *root;
    void pushdown(Node *node) {
        if (!node->ls) node->ls = new Node();
        if (!node->rs) node->rs = new Node();
        if (node->add == 0) return;
        node->ls->add = node->ls->val = node->add;
        node->rs->add = node->rs->val = node->add;
        node->add = 0;
    }
    void pushup(Node *node) {
        node->val = max(node->ls->val, node->rs->val);
    }
    int query(Node *node, int l, int r, int L, int R) {
        if (L <= l && r <= R) return node->val;
        pushdown(node);
        int mid = (l + r) >> 1, ans = 0;
        if (L <= mid) ans = query(node->ls, l, mid, L, R);
        if (R > mid) ans = max(ans, query(node->rs, mid + 1, r, L, R));
        return ans;
    }
    void update(Node *node, int l, int r, int L, int R, int v) {
        if (L <= l && r <= R) node->add = node->val = v;
        else {
            pushdown(node);
            int mid = (l + r) >> 1;
            if (L <= mid) update(node->ls, l, mid, L, R, v);
            if (R > mid) update(node->rs, mid + 1, r, L, R, v);
            pushup(node);
        }
    }
    vector<int> fallingSquares(vector<vector<int>>& positions) {
        vector<int> ans(positions.size());
        root = new Node();
        int i = 0;
        for (auto &p : positions) {
            int l = p[0], h = p[1], r = l + h - 1;
            int curr = query(root, 0, N, l, r);
            update(root, 0, N, l, r, curr + h);
            ans[i++] = root->val;
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    map<int, int> m; // [l, h], start from l, the height is h, until the next point.
    vector<int> fallingSquares(vector<vector<int>>& positions) {
        int n = positions.size(), i = 0;
        vector<int> ans(n);
        m[0] = 0;
        for (auto &p : positions) {
            int l = p[0], h = p[1], r = l + h - 1;
            auto lp = m.upper_bound(l), rp = m.upper_bound(r);
            int ph = prev(rp)->second;
            int piledHeight = 0;
            for (auto p = prev(lp); p != rp; ++p)
                piledHeight = max(piledHeight, p->second + h);
            m.erase(lp, rp);
            m[l] = piledHeight;
            if (rp == m.end() || rp->first != r + 1)
                m[r + 1] = ph;
            ans[i] = i ? max(ans[i - 1], piledHeight) : h;
            ++i;
        }
        return ans;
    }
};