3102.力扣每日一题7/9 Java（TreeMap）

博客主页：音符犹如代码
系列专栏：算法练习
关注博主，后期持续更新系列文章
如果有错误感谢请大家批评指出，及时修改
感谢大家点赞👍收藏⭐评论✍

TreeMap详解

解题思路

解题方法

时间复杂度

空间复杂度

Code

TreeMap 详解

TreeMap 是 Java 中的一种数据结构，属于 Map 接口的实现类之一。

主要特点：

有序性：TreeMap 中的键是按照自然顺序（对于实现了 Comparable 接口的键）或者自定义的比较器所定义的顺序进行存储和排序的。这使得遍历 TreeMap 时能按照特定的顺序获取键值对。
底层结构：其底层基于红黑树实现，红黑树是一种自平衡的二叉搜索树，保证了插入、删除和查找操作的平均时间复杂度为，其中 n 是键的数量。
键的要求：键必须是可比较的。如果键的类型没有实现 Comparable 接口，那么在创建 TreeMap 时必须提供一个自定义的比较器。

常见操作和方法：

put(K key, V value)：向 TreeMap 中添加键值对。
get(Object key)：根据给定的键获取对应的值。
containsKey(Object key)：检查 TreeMap 是否包含指定的键。
firstKey()：返回 TreeMap 中的第一个键。
lastKey()：返回 TreeMap 中的最后一个键。
lowerKey(K key)：返回小于指定键的最大键。
higherKey(K key)：返回大于指定键的最小键。

应用场景：

当需要按照键的特定顺序进行存储和访问时，例如需要对键进行有序遍历。
当需要快速查找特定范围内的键值对时，利用其有序性和相关的方法（如 subMap ）。

总的来说，TreeMap 提供了有序存储和操作键值对的功能，适用于对数据顺序有要求的场景。但在某些情况下，如果不关心顺序，使用 HashMap 可能在性能上更有优势，因为其操作的平均时间复杂度更低。

解题思路

首先，使用两个 TreeMap（xs 和 ys）分别对所有点的 x + y 和 y - x 的值进行计数。
然后通过遍历每个点，模拟移除该点后更新 TreeMap 中的计数。
计算更新后的 TreeMap 中键的最大值和最小值的差值（dx 和 dy），并与当前的最小最大距离 ans 进行比较和更新。

解题方法

初始化阶段：
- 创建两个 TreeMap 对象 xs 和 ys。
- 遍历输入的点数组 points ，对于每个点 p ，计算 x = p[0] + p[1] 和 y = p[1] - p[0] 。
- 使用 merge 方法将 x 和 y 及其出现次数累加到对应的 TreeMap 中。如果 x 或 y 已经存在，就将其计数加 1；如果不存在，就初始化为 1。
核心处理阶段：
- 初始化最小最大距离 ans 为 Integer.MAX_VALUE 。
- 再次遍历点数组 points 。
- 对于每个点，重新计算其对应的 x 和 y 。
- 检查 xs 中 x 的计数：
  - 如果计数为 1 ，则从 xs 中移除 x 。
  - 如果计数大于 1 ，则将其计数减 1 。
- 对 ys 中 y 进行类似的处理。
- 计算 xs 中最大键值和最小键值的差值 dx ，以及 ys 中最大键值和最小键值的差值 dy 。
- 取 dx 和 dy 中的最大值，与当前的 ans 比较并更新 ans 为较小值。
- 最后，如果 x 不在 xs 中，就将其添加并初始计数为 1 ；否则将其计数加 1 。对 y 在 ys 中的处理也是类似的。
最终返回 ans ，即恰好移除一个点后任意两点之间最大距离可能的最小值。

时间复杂度

初始化 TreeMap 的时间复杂度为O(n) ，其中 n 是点的数量。
对每个点进行处理的时间复杂度为O(n log n) ，因为涉及到对 TreeMap 的操作。
总的时间复杂度为 O(n²log n)

空间复杂度

使用了两个 TreeMap 来存储点的相关信息，空间复杂度为 O(n)

Code

import java.util.TreeMap;

class Solution {
    public int minimumDistance(int[][] points) {
        TreeMap<Integer, Integer> xs = new TreeMap<>();
        TreeMap<Integer, Integer> ys = new TreeMap<>();
        for (int[] p : points) {
            int x = p[0] + p[1];
            int y = p[1] - p[0];
            xs.merge(x, 1, Integer::sum);
            ys.merge(y, 1, Integer::sum);
        }

        int ans = Integer.MAX_VALUE;
        for (int[] p : points) {
            int x = p[0] + p[1];
            int y = p[1] - p[0];
            if (xs.get(x) == 1) {
                xs.remove(x);
            } else {
                xs.merge(x, -1, Integer::sum);
            }
            if (ys.get(y) == 1) {
                ys.remove(y);
            } else {
                ys.merge(y, -1, Integer::sum);
            }

            int dx = xs.lastKey() - xs.firstKey();
            int dy = ys.lastKey() - ys.firstKey();
            ans = Math.min(ans, Math.max(dx, dy));

            if (!xs.containsKey(x)) {
                xs.put(x, 1);
            } else {
                xs.merge(x, 1, Integer::sum);
            }
            if (!ys.containsKey(y)) {
                ys.put(y, 1);
            } else {
                ys.merge(y, 1, Integer::sum);
            }
        }
        return ans;
    }
}