作者： admin

目标

给你一个正整数 n，表示一个 n x n 的城市，同时给定一个二维数组 buildings，其中 buildings[i] = [x, y] 表示位于坐标 [x, y] 的一个 唯一 建筑。

如果一个建筑在四个方向（左、右、上、下）中每个方向上都至少存在一个建筑，则称该建筑 被覆盖 。

返回 被覆盖 的建筑数量。

示例 1：

输入: n = 3, buildings = [[1,2],[2,2],[3,2],[2,1],[2,3]]
输出: 1
解释:
只有建筑 [2,2] 被覆盖，因为它在每个方向上都至少存在一个建筑：
上方 ([1,2])
下方 ([3,2])
左方 ([2,1])
右方 ([2,3])
因此，被覆盖的建筑数量是 1。

示例 2：

输入: n = 3, buildings = [[1,1],[1,2],[2,1],[2,2]]
输出: 0
解释:
没有任何一个建筑在每个方向上都有至少一个建筑。

示例 3：

输入: n = 5, buildings = [[1,3],[3,2],[3,3],[3,5],[5,3]]
输出: 1
解释:
只有建筑 [3,3] 被覆盖，因为它在每个方向上至少存在一个建筑：
上方 ([1,3])
下方 ([5,3])
左方 ([3,2])
右方 ([3,5])
因此，被覆盖的建筑数量是 1。

说明：

• 2 <= n <= 10^5
• 1 <= buildings.length <= 10^5
• buildings[i] = [x, y]
• 1 <= x, y <= n
• buildings 中所有坐标均 唯一 。

思路

二维数组 buildings 表示建筑的坐标，如果建筑的上下左右均存在其它建筑，则称该建筑被包围。统计被包围建筑的个数。

只需记录每一行每一列的最大值与最小值，判断当前建筑是否在其中。

代码

/**
 * @date 2025-12-11 14:03
 */
public class CountCoveredBuildings3531 {

    public int countCoveredBuildings_v1(int n, int[][] buildings) {
        int[] minX = new int[n + 1];
        int[] maxX = new int[n + 1];
        int[] minY = new int[n + 1];
        int[] maxY = new int[n + 1];
        Arrays.fill(minX, n + 1);
        Arrays.fill(minY, n + 1);
        for (int[] building : buildings) {
            int x = building[0];
            int y = building[1];
            minX[y] = Math.min(minX[y], x);
            maxX[y] = Math.max(maxX[y], x);
            minY[x] = Math.min(minY[x], y);
            maxY[x] = Math.max(maxY[x], y);
        }
        int res = 0;
        for (int[] building : buildings) {
            int x = building[0];
            int y = building[1];
            if (x > minX[y] && x < maxX[y] && y > minY[x] && y < maxY[x]) {
                res++;
            }
        }
        return res;
    }

}

性能

目标

给你一个长度为 n 的数组 complexity。

在房间里有 n 台 上锁的 计算机，这些计算机的编号为 0 到 n - 1，每台计算机都有一个 唯一 的密码。编号为 i 的计算机的密码复杂度为 complexity[i]。

编号为 0 的计算机密码已经 解锁 ，并作为根节点。其他所有计算机必须通过它或其他已经解锁的计算机来解锁，具体规则如下：

• 可以使用编号为 j 的计算机的密码解锁编号为 i 的计算机，其中 j 是任何小于 i 的整数，且满足 complexity[j] < complexity[i]（即 j < i 并且 complexity[j] < complexity[i]）。
• 要解锁编号为 i 的计算机，你需要事先解锁一个编号为 j 的计算机，满足 j < i 并且 complexity[j] < complexity[i]。

求共有多少种 [0, 1, 2, ..., (n - 1)] 的排列方式，能够表示从编号为 0 的计算机（唯一初始解锁的计算机）开始解锁所有计算机的有效顺序。

由于答案可能很大，返回结果需要对 10^9 + 7 取余数。

注意：编号为 0 的计算机的密码已解锁，而 不是 排列中第一个位置的计算机密码已解锁。

排列 是一个数组中所有元素的重新排列。

示例 1：

输入： complexity = [1,2,3]
输出： 2
解释：
有效的排列有：
[0, 1, 2]
首先使用根密码解锁计算机 0。
使用计算机 0 的密码解锁计算机 1，因为 complexity[0] < complexity[1]。
使用计算机 1 的密码解锁计算机 2，因为 complexity[1] < complexity[2]。
[0, 2, 1]
首先使用根密码解锁计算机 0。
使用计算机 0 的密码解锁计算机 2，因为 complexity[0] < complexity[2]。
使用计算机 0 的密码解锁计算机 1，因为 complexity[0] < complexity[1]。

示例 2：

输入： complexity = [3,3,3,4,4,4]
输出： 0
解释：
没有任何排列能够解锁所有计算机。

说明：

• 2 <= complexity.length <= 10^5
• 1 <= complexity[i] <= 10^9

思路

如果要解锁所有计算机，第一台的复杂度必须是唯一最小值。因此可以用第一台解锁后面所有计算机，排列数为 (n - 1)!。

代码

/**
 * @date 2025-12-10 9:06
 */
public class CountPermutations3577 {

    public int countPermutations(int[] complexity) {
        int mod = 1000000007;
        int res = 1;
        int n = complexity.length;
        long c = 1;
        int min = complexity[0];
        for (int i = 1; i < n; i++) {
            if (complexity[i] <= min) {
                return 0;
            }
            res = (int) ((res * c++) % mod);
        }
        return res;
    }

}

性能

目标

给你一个整数数组 nums。

特殊三元组 定义为满足以下条件的下标三元组 (i, j, k)：

• 0 <= i < j < k < n，其中 n = nums.length
• nums[i] == nums[j] * 2
• nums[k] == nums[j] * 2

返回数组中 特殊三元组 的总数。

由于答案可能非常大，请返回结果对 10^9 + 7 取余数后的值。

示例 1：

输入： nums = [6,3,6]
输出： 1
解释：
唯一的特殊三元组是 (i, j, k) = (0, 1, 2)，其中：
nums[0] = 6, nums[1] = 3, nums[2] = 6
nums[0] = nums[1] * 2 = 3 * 2 = 6
nums[2] = nums[1] * 2 = 3 * 2 = 6

示例 2：

输入： nums = [0,1,0,0]
输出： 1
解释：
唯一的特殊三元组是 (i, j, k) = (0, 2, 3)，其中：
nums[0] = 0, nums[2] = 0, nums[3] = 0
nums[0] = nums[2] * 2 = 0 * 2 = 0
nums[3] = nums[2] * 2 = 0 * 2 = 0

示例 3：

输入： nums = [8,4,2,8,4]
输出： 2
解释：
共有两个特殊三元组：
(i, j, k) = (0, 1, 3)
nums[0] = 8, nums[1] = 4, nums[3] = 8
nums[0] = nums[1] * 2 = 4 * 2 = 8
nums[3] = nums[1] * 2 = 4 * 2 = 8
(i, j, k) = (1, 2, 4)
nums[1] = 4, nums[2] = 2, nums[4] = 4
nums[1] = nums[2] * 2 = 2 * 2 = 4
nums[4] = nums[2] * 2 = 2 * 2 = 4

说明：

• 3 <= n == nums.length <= 10^5
• 0 <= nums[i] <= 10^5

思路

找到数组 nums 的三元组 (i, j, k) 满足 nums[i] == nums[k] == 2 * nums[j]，返回特殊三元组的个数。注意这里三元组是元素下标所以不会重复。

枚举右端点，如果为偶数，查找中间元素 nums[k]/2 作为右端点的二元组个数，该二元组 (i, j) 可以同时维护，找到左侧 i 的个数，满足 nums[i] == 2 * nums[j]。

代码

/**
 * @date 2025-12-09 8:55
 */
public class SpecialTriplets3583 {

    public int specialTriplets_v1(int[] nums) {
        int n = nums.length;
        int mod = 1000000007;
        Map<Integer, Long> cnt = new HashMap<>();
        Map<Integer, Long> binaryCnt = new HashMap<>();
        long res = 0;
        for (int i = 0; i < n; i++) {
            if (nums[i] % 2 == 0) {
                res += binaryCnt.getOrDefault(nums[i] / 2, 0L);
            }
            binaryCnt.merge(nums[i], cnt.getOrDefault(nums[i] * 2, 0L), Long::sum);
            cnt.merge(nums[i], 1L, Long::sum);
        }
        return (int) (res % mod);
    }

}

性能

目标

给你一个整数数组 nums 和一个整数 k。你的任务是将 nums 分割成一个或多个 非空 的连续子段，使得每个子段的 最大值 与 最小值 之间的差值 不超过 k。

返回在此条件下将 nums 分割的总方法数。

由于答案可能非常大，返回结果需要对 10^9 + 7 取余数。

示例 1：

输入： nums = [9,4,1,3,7], k = 4
输出： 6
解释：
共有 6 种有效的分割方式，使得每个子段中的最大值与最小值之差不超过 k = 4：
[[9], [4], [1], [3], [7]]
[[9], [4], [1], [3, 7]]
[[9], [4], [1, 3], [7]]
[[9], [4, 1], [3], [7]]
[[9], [4, 1], [3, 7]]
[[9], [4, 1, 3], [7]]

示例 2：

输入： nums = [3,3,4], k = 0
输出： 2
解释：
共有 2 种有效的分割方式，满足给定条件：
[[3], [3], [4]]
[[3, 3], [4]]

说明：

• 2 <= nums.length <= 5 * 10^4
• 1 <= nums[i] <= 10^9
• 0 <= k <= 10^9

思路

划分数组 nums，使得每一个子数组的最大最小值之差不超过 k，求划分的总方法数。

定义 dp[i] 表示 [0, i] 满足条件的划分数，dp[i + 1] = Σdp[j] j∈[l, i]，l 是固定右端点后满足条件的最小下标。

枚举满足条件的最小下标时可以使用滑动窗口，使用单调栈来维护窗口的最大值与最小值。

代码

/**
 * @date 2025-12-09 9:38
 */
public class CountPartitions3578 {

    public int countPartitions(int[] nums, int k) {
        Deque<Integer> max = new ArrayDeque<>();
        Deque<Integer> min = new ArrayDeque<>();
        int mod = 1000000007;
        int n = nums.length;
        long[] dp = new long[n + 1];
        dp[0] = 1;
        int l = 0;
        long window = 0;
        for (int r = 0; r < n; r++) {
            while (!max.isEmpty() && max.peekLast() < nums[r]) {
                max.pollLast();
            }
            while (!min.isEmpty() && min.peekLast() > nums[r]) {
                min.pollLast();
            }
            max.offer(nums[r]);
            min.offer(nums[r]);
            int diff = max.peek() - min.peek();

            window += dp[r];
            while (l <= r && diff > k) {
                if (max.peek() == nums[l]) {
                    max.poll();
                }
                if (min.peek() == nums[l]) {
                    min.poll();
                }
                diff = max.peek() - min.peek();
                window -= dp[l++];
            }
            dp[r + 1] = window % mod;
        }
        return (int) (dp[n] % mod);
    }

}

性能

目标

在一条无限长的公路上有 n 辆汽车正在行驶。汽车按从左到右的顺序按从 0 到 n - 1 编号，每辆车都在一个 独特的 位置。

给你一个下标从 0 开始的字符串 directions ，长度为 n 。directions[i] 可以是 'L'、'R' 或 'S' 分别表示第 i 辆车是向 左 、向 右 或者 停留 在当前位置。每辆车移动时 速度相同 。

碰撞次数可以按下述方式计算：

• 当两辆移动方向 相反 的车相撞时，碰撞次数加 2 。
• 当一辆移动的车和一辆静止的车相撞时，碰撞次数加 1 。

碰撞发生后，涉及的车辆将无法继续移动并停留在碰撞位置。除此之外，汽车不能改变它们的状态或移动方向。

返回在这条道路上发生的 碰撞总次数 。

示例 1：

输入：directions = "RLRSLL"
输出：5
解释：
将会在道路上发生的碰撞列出如下：
- 车 0 和车 1 会互相碰撞。由于它们按相反方向移动，碰撞数量变为 0 + 2 = 2 。
- 车 2 和车 3 会互相碰撞。由于 3 是静止的，碰撞数量变为 2 + 1 = 3 。
- 车 3 和车 4 会互相碰撞。由于 3 是静止的，碰撞数量变为 3 + 1 = 4 。
- 车 4 和车 5 会互相碰撞。在车 4 和车 3 碰撞之后，车 4 会待在碰撞位置，接着和车 5 碰撞。碰撞数量变为 4 + 1 = 5 。
因此，将会在道路上发生的碰撞总次数是 5 。

示例 2：

输入：directions = "LLRR"
输出：0
解释：
不存在会发生碰撞的车辆。因此，将会在道路上发生的碰撞总次数是 0 。

说明：

• 1 <= directions.length <= 10^5
• directions[i] 的值为 'L'、'R' 或 'S'

思路

无限长的公路上有 n 辆车在行驶，假设公路只有一个车道，directions[i] 表示汽车的行驶方向，L R S 分别表示 左、右、停留三种状态。如果相向而行碰撞次数 +2，装上静止的汽车碰撞次数 +1，发生碰撞后状态均变为停留。返回公路上发生的总碰撞次数。

将行驶方向相同的视为一组，

• 如果当前组行驶方向是 L，并且前面一组是 R，那么碰撞次数为 cntL + cntR，如果前面一组是 S，则碰撞次数为 cntL。
• 如果当前组行驶方向是 S，并且前面一组是 R，那么碰撞次数为 cntR。
• 注意碰撞之后状态变为 S。

代码

/**
 * @date 2025-12-04 9:33
 */
public class CountCollisions2211 {

    public int countCollisions(String directions) {
        int res = 0;
        char[] chars = directions.toCharArray();
        int n = chars.length;
        int i = 0;
        int prevCnt = 0;
        char prev = 'L';
        while (i < n) {
            int start = i;
            while (i < n && chars[i] == chars[start]) {
                i++;
            }
            if (prevCnt != 0) {
                if (chars[start] == 'S' && prev == 'R') {
                    res += prevCnt;
                } else if (chars[start] == 'L' && prev == 'R') {
                    res += prevCnt + i - start;
                    chars[start] = 'S';
                } else if (chars[start] == 'L' && prev == 'S') {
                    res += i - start;
                    chars[start] = 'S';
                }
            }
            prevCnt = i - start;
            prev = chars[start];
        }
        return res;
    }
}

性能