标签： medium

目标

给你一个整数数组 prices ，表示一支股票的历史每日股价，其中 prices[i] 是这支股票第 i 天的价格。

一个 平滑下降的阶段 定义为：对于 连续一天或者多天 ，每日股价都比 前一日股价恰好少 1 ，这个阶段第一天的股价没有限制。

请你返回 平滑下降阶段 的数目。

示例 1：

输入：prices = [3,2,1,4]
输出：7
解释：总共有 7 个平滑下降阶段：
[3], [2], [1], [4], [3,2], [2,1] 和 [3,2,1]
注意，仅一天按照定义也是平滑下降阶段。

示例 2：

输入：prices = [8,6,7,7]
输出：4
解释：总共有 4 个连续平滑下降阶段：[8], [6], [7] 和 [7]
由于 8 - 6 ≠ 1 ，所以 [8,6] 不是平滑下降阶段。

示例 3：

输入：prices = [1]
输出：1
解释：总共有 1 个平滑下降阶段：[1]

说明：

• 1 <= prices.length <= 10^5
• 1 <= prices[i] <= 10^5

思路

求满足要求的子数组个数，要求子数组严格单调递减且相邻元素差为 1。

枚举右端点 r，假设满足条件的最小的左端点为 l，那么以 r 为右端点且满足条件的子数组个数为 r - l + 1。对于每一个 r，无需重复判断最小的 l，它可以从前一个状态转移过来，即如果 prices[r - 1] - prices[r] == 1 那么 l 仍是以 r - 1 为右端点且满足条件的最小左端点，否则 l = r。

代码

/**
 * @date 2025-12-15 9:10
 */
public class GetDescentPeriods2110 {

    public long getDescentPeriods(int[] prices) {
        long res = 0L;
        int l = 0;
        int n = prices.length;
        int prev = prices[0] + 1;
        for (int r = 0; r < n; r++) {
            if (prev - prices[r] != 1){
                l = r;
            }
            res += r - l + 1;
            prev = prices[r];
        }
        return res;
    }
}

性能

目标

给你一个正整数 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;
    }
}

性能

目标

给你一个二维整数数组 points，其中 points[i] = [xi, yi] 表示第 i 个点在笛卡尔平面上的坐标。

水平梯形 是一种凸四边形，具有 至少一对 水平边（即平行于 x 轴的边）。两条直线平行当且仅当它们的斜率相同。

返回可以从 points 中任意选择四个不同点组成的 水平梯形 数量。

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

示例 1：

输入： points = [[1,0],[2,0],[3,0],[2,2],[3,2]]
输出： 3
解释：
有三种不同方式选择四个点组成一个水平梯形：
使用点 [1,0]、[2,0]、[3,2] 和 [2,2]。
使用点 [2,0]、[3,0]、[3,2] 和 [2,2]。
使用点 [1,0]、[3,0]、[3,2] 和 [2,2]。

示例 2：

输入： points = [[0,0],[1,0],[0,1],[2,1]]
输出： 1
解释：
只有一种方式可以组成一个水平梯形。

说明：

• 4 <= points.length <= 10^5
• –10^8 <= xi, yi <= 10^8
• 所有点两两不同。

思路

有一些二维平面中的点 points，从中选取四个点组成水平梯形，返回水平梯形的数目。

水平梯形是有一对边平行于 x 轴的梯形。直接的想法是根据纵坐标分组，选两组，每组中选两个点。

可以直接计算每组的组合数 C(n, 2) = n * (n - 1) / 2，计算分组组合数的后缀和，根据乘法原理计算即可。

代码

/**
 * @date 2025-12-02 0:14
 */
public class CountTrapezoids2623 {

    /**
     * 执行通过
     */
    public int countTrapezoids(int[][] points) {
        Map<Integer, Integer> cnt = new HashMap<>();
        for (int[] point : points) {
            cnt.merge(point[1], 1, Integer::sum);
        }
        int mod = 1000000007;
        for (Map.Entry<Integer, Integer> entry : cnt.entrySet()) {
            Integer c = entry.getValue();
            cnt.put(entry.getKey(), (int) ((c * (c - 1L) / 2) % mod));
        }
        int[] comb = cnt.values().stream().mapToInt(x -> x).toArray();
        int n = comb.length;
        int[] suffix = new int[n + 1];
        for (int i = n - 1; i >= 0; i--) {
            suffix[i] = (suffix[i + 1] + comb[i]) % mod;
        }
        long res = 0L;
        for (int i = 0; i < n; i++) {
            res = (res + ((long) comb[i] * suffix[i + 1])) % mod;
        }
        return (int) res;
    }
}

性能

目标

给你一个正整数数组 nums，请你移除 最短 子数组（可以为 空），使得剩余元素的 和 能被 p 整除。 不允许 将整个数组都移除。

请你返回你需要移除的最短子数组的长度，如果无法满足题目要求，返回 -1 。

子数组 定义为原数组中连续的一组元素。

示例 1：

输入：nums = [3,1,4,2], p = 6
输出：1
解释：nums 中元素和为 10，不能被 p 整除。我们可以移除子数组 [4] ，剩余元素的和为 6 。

示例 2：

输入：nums = [6,3,5,2], p = 9
输出：2
解释：我们无法移除任何一个元素使得和被 9 整除，最优方案是移除子数组 [5,2] ，剩余元素为 [6,3]，和为 9 。

示例 3：

输入：nums = [1,2,3], p = 3
输出：0
解释：和恰好为 6 ，已经能被 3 整除了。所以我们不需要移除任何元素。

示例 4：

输入：nums = [1,2,3], p = 7
输出：-1
解释：没有任何方案使得移除子数组后剩余元素的和被 7 整除。

示例 5：

输入：nums = [1000000000,1000000000,1000000000], p = 3
输出：0

说明：

• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^9
• 1 <= p <= 10^9

思路

有一个正整数数组 nums，需要移除一个最短子数组（可以为空），使得剩余元素的和能被 p 整除，返回移除的最短子数组长度，如果无法满足返回 -1。

计算数组和，求出余数 rem，使用哈希表 lastIndex 记录前缀和余数的最大下标，根据当前前缀和的余数，计算需要保留的前缀数组 [0, lastIndex.get((curRem - rem + p) % p)]，计算得到需要减去的子数组 [lastIndex.get((curRem - rem + p) % p) + 1, i] 它的和模 p 余 rem，取长度的最小值即可。

代码

/**
 * @date 2025-11-30 10:41
 */
public class MinSubarray1590 {

    public int minSubarray(int[] nums, int p) {
        int n = nums.length;
        long sum = 0;
        for (int num : nums) {
            sum += num;
        }
        int rem = (int) (sum % p);
        if (rem == 0) {
            return 0;
        }
        Map<Integer, Integer> lastIndex = new HashMap<>();
        lastIndex.putIfAbsent(0, -1);
        int curRem = 0;
        int res = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            curRem = (curRem + nums[i]) % p;
            int prev = (p + curRem - rem) % p;
            res = Math.min(res, i - lastIndex.getOrDefault(prev, -n));
            lastIndex.put(curRem, i);
        }
        return res == n ? -1 : res;
    }

}

性能

目标

给你一个整数数组 nums 和一个整数 k 。

返回 nums 中一个 非空子数组 的 最大 和，要求该子数组的长度可以 被 k 整除。

示例 1：

输入： nums = [1,2], k = 1
输出： 3
解释：
子数组 [1, 2] 的和为 3，其长度为 2，可以被 1 整除。

示例 2：

输入： nums = [-1,-2,-3,-4,-5], k = 4
输出： -10
解释：
满足题意且和最大的子数组是 [-1, -2, -3, -4]，其长度为 4，可以被 4 整除。

示例 3：

输入： nums = [-5,1,2,-3,4], k = 2
输出： 4
解释：
满足题意且和最大的子数组是 [1, 2, -3, 4]，其长度为 4，可以被 2 整除。

说明：

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

思路

计算长度能被 k 整除的子数组的最大元素和。

核心点是维护同余前缀和的最小值。

也有网友使用滑窗加动态规划来做，滑窗计算 长度为 k 的子数组和，动态规划累加长度 m * k 的子数组和，这里使用了贪心策略，如果前面的子数组和小于 0，直接重置为 0。

代码

/**
 * @date 2025-11-27 9:06
 */
public class MaxSubarraySum3381 {

    public long maxSubarraySum(int[] nums, int k) {
        int n = nums.length;
        long[] prefix = new long[n + 1];
        for (int i = 1; i <= n; i++) {
            prefix[i] = prefix[i - 1] + nums[i - 1];
        }
        long[] minPrefix = new long[k];
        Arrays.fill(minPrefix, Long.MAX_VALUE / 2);
        long res = Long.MIN_VALUE;
        for (int i = 0; i <= n; i++) {
            int rem = i % k;
            res = Math.max(res, prefix[i] - minPrefix[rem]);
            minPrefix[rem] = Math.min(minPrefix[rem], prefix[i]);
        }
        return res;
    }

}

性能