堆积木

public class Solution_wei {
    public int buildingBlocks(int[][] blocks) {
        int len = blocks.length;
        if (len == 0) {
            return 0;
        }
        // 最后的返回值
        int result = 0;
        // 保证长 > 宽
        for (int i = 0; i < len; i++) {
            if (blocks[i][0] < blocks[i][1]) {
                int[] block = blocks[i];
                int temp = block[0];
                block[0] = block[1];
                block[1] = temp;
            }
        }
        // 按第一维的增序排列
        // 按第二维降序
        Arrays.sort(blocks, (a1, a2) -> {
            return a1[0] != a2[0] ? a1[0] - a2[0] : a2[1] - a1[1];
        } );
        int[] dp = new int[len];
        Arrays.fill(dp, 1);
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < i; j++) {
                if (blocks[i][1] >= blocks[j][1]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }
        // 找到最大值
        for (int i = 0; i < len; i++) {
            result = Math.max(result, dp[i]);
        }
        return result;
    }
    public static void main(String[] args) {
        int[][] blocks = {
                {5, 4},
                {6, 3},
                {6, 7},
                {6, 6}
        };
        int[][] blocks2 = {
                {5, 4},
                {6, 3},
                {6, 7},
                {6, 6},
                {4, 6}
        };
        Solution_wei obj = new Solution_wei();
        int i = obj.buildingBlocks(blocks);
        System.out.println(i);
        int j = obj.buildingBlocks(blocks2);
        System.out.println(j);
    }
}