在二維平面上的 x 軸上肮街，放置著一些方塊怖喻。

給你一個(gè)二維整數(shù)數(shù)組 positions ，其中 positions[i] = [lefti, sideLengthi] 表示：第 i 個(gè)方塊邊長(zhǎng)為 sideLengthi 今膊，其左側(cè)邊與 x 軸上坐標(biāo)點(diǎn) lefti 對(duì)齊。

每個(gè)方塊都從一個(gè)比目前所有的落地方塊更高的高度掉落而下吉嚣。方塊沿 y 軸負(fù)方向下落观话，直到著陸到 另一個(gè)正方形的頂邊 或者是 x 軸上 。一個(gè)方塊僅僅是擦過另一個(gè)方塊的左側(cè)邊或右側(cè)邊不算著陸轴或。一旦著陸昌跌，它就會(huì)固定在原地，無法移動(dòng)照雁。

在每個(gè)方塊掉落后蚕愤，你必須記錄目前所有已經(jīng)落穩(wěn)的 方塊堆疊的最高高度 。
返回一個(gè)整數(shù)數(shù)組 ans ，其中 ans[i] 表示在第 i 塊方塊掉落后堆疊的最高高度萍诱。
輸入：positions = [[1,2],[2,3],[6,1]]
輸出：[2,5,5]
解釋：
第 1 個(gè)方塊掉落后悬嗓，最高的堆疊由方塊 1 組成，堆疊的最高高度為 2 裕坊。
第 2 個(gè)方塊掉落后包竹，最高的堆疊由方塊 1 和 2 組成，堆疊的最高高度為 5 
第 3 個(gè)方塊掉落后籍凝，最高的堆疊仍然由方塊 1 和 2 組成周瞎，堆疊的最高高度為 5 。
因此饵蒂，返回 [2, 5, 5] 作為答案声诸。
。

package 分段樹;

import java.util.*;

//leetcode submit region begin(Prohibit modification and deletion)
class FallingSquares699 {

    //    public List<Integer> fallingSquares(int[][] positions) {
//        Set<int[]> set = new TreeSet<>(new Comparator<int[]>() {
//            @Override
//            public int compare(int[] o1, int[] o2) {
//                return o1[0] - o2[0];
//            }
//        });
//        List<Integer> res = new ArrayList<>();
//        res.add(positions[0][1]);
//        set.add(new int[]{positions[0][0], positions[0][0]+positions[0][1], positions[0][1]});
//        int curMaxHight = 0;
//        for (int i = 1; i < positions.length; i++) {
//            int[] curArr = new int[]{positions[i][0], positions[i][0]+positions[i][1], positions[i][1]};
//            List<int[]> list = new ArrayList<>();
//            boolean isOver = true;
//            while (set.size() != 0) {
//                int[] curSetArr = ((TreeSet<int[]>) set).pollFirst();
//                if (curArr[1] <= curSetArr[0]) {
//                    set.add(new int[]{curArr[0], curArr[1], curMaxHight+curArr[2]});
//                    set.add(curSetArr);
//                    curMaxHight = curMaxHight+curArr[2];
//                    isOver = true;
//                    break;
//                } else if (curArr[0] <= curSetArr[0] && curArr[1] <= curSetArr[1]) {
//                    set.add(new int[]{curArr[0], curArr[1], Math.max(curMaxHight, curSetArr[2])+curArr[2]});
//                    if (curArr[1] < curSetArr[1]) {
//                        set.add(new int[]{curArr[1], curSetArr[1], curSetArr[2]});
//                    }
//                    isOver = true;
//                    curMaxHight = Math.max(curMaxHight, Math.max(curMaxHight, curSetArr[2])+curArr[2]);
//                    break;
//                } else if (curArr[0] <= curSetArr[0] && curArr[1] > curSetArr[1]) {
//                    curMaxHight = 0;
//                    curMaxHight = Math.max(curMaxHight, curSetArr[2]);
//                    isOver = false;
////                    curArr[2] = curMaxHight;
//                } else if (curArr[0] >= curSetArr[1]) {
//                    curMaxHight = 0;
//                    list.add(new int[]{curSetArr[0], curSetArr[1], curSetArr[2]});
//                    isOver = false;
//                } else if (curArr[0] >= curSetArr[0] && curArr[1] <= curSetArr[1]) {
//                    if (curArr[0] > curSetArr[0]) {
//                        set.add(new int[]{curSetArr[0], curArr[1], curSetArr[2]});
//                    }
//                    set.add(new int[]{curArr[0], curArr[1], curArr[2]+Math.max(curMaxHight, curSetArr[2])});
//                    if (curArr[1] < curSetArr[1]) {
//                        set.add(new int[]{curArr[0], curSetArr[1], curSetArr[2]});
//                    }
//                    curMaxHight = Math.max(curMaxHight, Math.max(curMaxHight, curSetArr[2])+curArr[2]);
//                    isOver = true;
//                    break;
//                } else if (curArr[0] >= curSetArr[0] && curArr[1] > curSetArr[1]) {
//                    curMaxHight = 0;
//                    if (curArr[0] > curSetArr[0]) {
//                        list.add(new int[]{curSetArr[0], curArr[0], curSetArr[2]});
//                    }
//                    curMaxHight = Math.max(curMaxHight, curSetArr[2]);
//                    isOver = false;
////                    curArr[2] = curMaxHight;
//                }
//            }
//            if (!isOver) {
//                set.add(new int[]{curArr[0], curArr[1], curArr[2]+curMaxHight});
//            }
//            for (int j = 0; j < list.size(); j++) {
//                set.add(list.get(j));
//            }
//            int currentMax = 0;
//            Iterator<int[]> iteratorSet = set.iterator();
//            while(iteratorSet.hasNext()){
//                currentMax = Math.max(iteratorSet.next()[2], currentMax);
//            }
//            res.add(currentMax);
//        }
//        return res;
//    }
    public List<Integer> fallingSquares(int[][] positions) {
        int n = positions.length;
        List<Integer> heights = new ArrayList<Integer>();
        for (int i = 0; i < n; i++) {
            int left1 = positions[i][0], right1 = positions[i][0] + positions[i][1] - 1;
            int height = positions[i][1];
            for (int j = 0; j < i; j++) {
                int left2 = positions[j][0], right2 = positions[j][0] + positions[j][1] - 1;
                if (right1 >= left2 && right2 >= left1) {
                    height = Math.max(height, heights.get(j) + positions[i][1]);
                }
            }
            heights.add(height);
        }
        for (int i = 1; i < n; i++) {
            heights.set(i, Math.max(heights.get(i), heights.get(i - 1)));
        }
        return heights;
    }


    public static void main(String[] args) {
        FallingSquares699 so = new FallingSquares699();

        List<Integer> a = so.fallingSquares(new int[][]{
                {4, 9}, {8, 8}, {6, 8}, {1, 2}
        });
        int b = 1;
    }
}
//leetcode submit region end(Prohibit modification and deletion)