阿坤老师的独特瓷器(Java详解)

一、题目描述

示例：

输入：

5

3 4

5 6

2 5

3 7

6 5

 输出：

3

二、题解

思路分析：

题目要求我们计算出“独特瓷器”的个数，而“独特瓷器”是指对于瓷器A，没有另一个瓷器B，直径和高度都大于A。则当有瓷器的直径和高度都大于A时，A不为“独特瓷器”。因此，最简单的方法是通过循环来遍历这N个瓷器，分别判断其是否为“独特瓷器”。然而，由于其使用了双重for循环，会导致部分测试用例运行超时，而导致测试失败

由于只有当瓷器B的直径和高度都大于A时，A才不能为“独特瓷器”，因此我们可以先按照瓷器的直径d（或是高度h）按照从大到小的规则来对这些瓷器按进行排序，这样，瓷器A前面的所有瓷器直径d都大于或等于瓷器A的直径，而当直径d相同时，我们则按照高度h从小到大排序

为什么要这样排序？

当我们将瓷器以d从大到小进行排序，则表明瓷器A前面的所有瓷器的直径d都大于或等于A的直径d，此时，我们只需要判断瓷器的高度h，假设瓷器A前面的所有瓷器直径d都大于A的d(等于的情况后面会讨论)，则瓷器A前面有一个瓷器的h大于A的h，则表明A不是“独特瓷器”，此时我们只需以前面瓷器h的最大值来和A的h进行比较，就可以判断出A是否是“独特瓷器”

为什么当d相同时要以h进行从小到大排序？

当d相同时，若将h更大的瓷器B排在A前面，则瓷器高度的最大值max必定大于A，A被判断为不是“独特瓷器”，然而，A的d与B的d相同，不满足B的d和h都大于A，因此，A是“独特瓷器”。所以，当d相同时，我们要将h较小的瓷器A排在前面，先判断A是否为“独特瓷器”，再判断h较大的瓷器B是否为独特瓷器。

实现步骤：

1. 将这n个瓷器的直径d和高h存放到二维数组中

2. 将瓷器以d按从大到小进行排序，当d相同时，以h从小到大进行排序

如何实现二维数组的排序？

我们可以使用Arrays.sort()来实现二维数组的排序。由于Arrays.sort()只能对一维数组进行排序，而对于二维数组，则需要使用自定义的Comparator

Comparator是一个专用的比较器，当对象不支撑自比较或是自比较函数不能满足需求时，可以使用比较器来完成两个对象之间大小的比较

如何实现Comparator接口？

我们需要以d降序排序，当d相同时，以h升序排序

（1）自定义类

定义类MyComparator继承于Comparator<>，并重写compare方法

class MyComparator implements Comparator<int[]>{
    @Override
     public int compare(int[] o1, int[] o2) {
        //当直径d相同时，按h升序排序
        if(Integer.compare(o1[0],o2[0]) == 0){
            return Integer.compare(o1[1],o2[1]);
        }else {
            //直径d不同时，以d降序排序
            return Integer.compare(o2[0],o1[0]);
        }
    }
}

Arrays.sort(porcelain,new MyComparator());

（2）匿名内部类

Arrays.sort(porcelain, new Comparator<int[]>() {
    @Override
    public int compare(int[] o1, int[] o2) {
        //当直径d相同时，按h升序排序
        if(Integer.compare(o1[0],o2[0]) == 0){
            return Integer.compare(o1[1],o2[1]);
        }else {
            //直径d不同时，以d降序排序
            return Integer.compare(o2[0],o1[0]);
        }
    }
});

（3）lambda表达式

Arrays.sort(porcelain, (o1, o2) -> {
    //当直径d相同时，按h升序排序
    if(Integer.compare(o1[0],o2[0]) == 0){
        return Integer.compare(o1[1],o2[1]);
    }else {
        //直径d不同时，以d降序排序
        return Integer.compare(o2[0],o1[0]);
    }
});

3. 定义瓷器的最大高度maxH=0（瓷器的高度不可能为负数），遍历这N个瓷器，判断其是否为“独特瓷器”，统计“独特瓷器”的个数

代码实现：

import java.util.Arrays;
import java.util.Scanner;

public class Test {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        //在此输入您的代码...
        int n = scan.nextInt();
        //将这n个瓷器的直径d和高h存放到二维数组中
        int[][] porcelain = new int[n][2];
        for (int i = 0; i < n; i++) {
            porcelain[i][0] = scan.nextInt();
            porcelain[i][1] = scan.nextInt();
        }

        //排序
        //按照直径d降序排序，若d相同，则按照高度h升序排序
        Arrays.sort(porcelain, (o1, o2) -> {
            //当直径d相同时，按h升序排序
            if(Integer.compare(o1[0],o2[0]) == 0){
                return Integer.compare(o1[1],o2[1]);
            }else {
                //直径d不同时，以d降序排序
                return Integer.compare(o2[0],o1[0]);
            }
        });

        //定义最大高度maxH,遍历这n个瓷器，判断其是否为“独特瓷器”
        int maxH = 0;
        int count = 0;
        for (int i = 0; i < n; i++) {
            if(porcelain[i][1] >= maxH){
                count++;
                maxH = porcelain[i][1];
            }
        }
        //输出独特瓷器的个数
        System.out.println(count);
    }
}

题目来自：

阿坤老师的独特瓷器 – 蓝桥云课 (lanqiao.cn)