对于每个瓷器,它都有一个直径和高度。对于此类问题,我们常用的手段是将每个瓷器看作是一个二维空间中的点(对于本题而言就是看看该点的右上角是否有点),然后再尝试将二维空间上的问题转化为了一维空间上的问题,从而简化问题的复杂度。
基于上述分析,可以先固定一个点去比较另一个变量来判定是否是“独特瓷器”,固定采用排序,将先将d倒序,再将h升序,那么便利每一个物品pp[i]只需要比较是否>=max_h,如果大于计数++ : d倒序排序保证当前的pp[i].d一定<=max_d,那么想要看看是否是独特瓷器,只需要pp[i].h>=max_h ? “说明该点的右上角没有点(不包括边界)” : “相反情况”
import java.util.*;
public class Main {
static final int N = 100010;
static Pair[] pp = new Pair[N];
static int n;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
for (int i = 1; i <= n; i++) {
pp[i] = new Pair(sc.nextInt(), sc.nextInt());
}
Arrays.sort(pp, 1, n + 1, (o1, o2) -> {
if (o1.d != o2.d) return o2.d - o1.d;
return o1.h - o2.h;
});
int ans = 0, maxh = 0;
for (int i = 1; i <= n; i++) {
if (pp[i].h >= maxh) {
ans++;
maxh = pp[i].h;
}
}
System.out.println(ans);
sc.close();
}
}
class Pair {
int d, h;
public Pair(int d, int h) {
this.d = d;
this.h = h;
}
}