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

深藏阁楼爱情的钟 2024-02-18 11:13 7阅读 0赞

## 一、题目描述 ##

![292444f99045488b9ec254e7d6d9d66a.png][]

**示例：**

**输入：**

> **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)][- _ _lanqiao.cn]

[292444f99045488b9ec254e7d6d9d66a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/18/68376648f8f14471acd5abb3a7c048a0.png
[- _ _lanqiao.cn]: https://www.lanqiao.cn/problems/3994/learning/