刷题进行时-线段树-699. 掉落的方块

在二维平面上的 x 轴上，放置着一些方块。

给你一个二维整数数组 positions ，其中 positions[i] = [lefti, sideLengthi] 表示：第 i 个方块边长为 sideLengthi ，其左侧边与 x 轴上坐标点 lefti 对齐。

每个方块都从一个比目前所有的落地方块更高的高度掉落而下。方块沿 y 轴负方向下落，直到着陆到 另一个正方形的顶边 或者是 x 轴上 。一个方块仅仅是擦过另一个方块的左侧边或右侧边不算着陆。一旦着陆，它就会固定在原地，无法移动。

在每个方块掉落后，你必须记录目前所有已经落稳的 方块堆叠的最高高度 。
返回一个整数数组 ans ，其中 ans[i] 表示在第 i 块方块掉落后堆叠的最高高度。
输入：positions = [[1,2],[2,3],[6,1]]
输出：[2,5,5]
解释：
第 1 个方块掉落后，最高的堆叠由方块 1 组成，堆叠的最高高度为 2 。
第 2 个方块掉落后，最高的堆叠由方块 1 和 2 组成，堆叠的最高高度为 5 
第 3 个方块掉落后，最高的堆叠仍然由方块 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)