hard – 第 3 页 – shelterofly

目标

给你 3 个正整数 zero ，one 和 limit 。

一个二进制数组 arr 如果满足以下条件，那么我们称它是稳定的：

0 在 arr 中出现次数恰好为 zero 。
1 在 arr 中出现次数恰好为 one 。
arr 中每个长度超过 limit 的子数组都同时包含 0 和 1 。

请你返回稳定二进制数组的总数目。

由于答案可能很大，将它对 10^9 + 7 取余后返回。

示例 1：

输入：zero = 1, one = 1, limit = 2
输出：2
解释：
两个稳定的二进制数组为 [1,0] 和 [0,1] ，两个数组都有一个 0 和一个 1 ，且没有子数组长度大于 2 。

示例 2：

输入：zero = 1, one = 2, limit = 1
输出：1
解释：
唯一稳定的二进制数组是 [1,0,1] 。
二进制数组 [1,1,0] 和 [0,1,1] 都有长度为 2 且元素全都相同的子数组，所以它们不稳定。

示例 3：

输入：zero = 3, one = 3, limit = 2
输出：14
解释：
所有稳定的二进制数组包括 [0,0,1,0,1,1] ，[0,0,1,1,0,1] ，[0,1,0,0,1,1] ，[0,1,0,1,0,1] ，[0,1,0,1,1,0] ，[0,1,1,0,0,1] ，[0,1,1,0,1,0] ，[1,0,0,1,0,1] ，[1,0,0,1,1,0] ，[1,0,1,0,0,1] ，[1,0,1,0,1,0] ，[1,0,1,1,0,0] ，[1,1,0,0,1,0] 和 [1,1,0,1,0,0] 。

说明：

1 <= zero, one, limit <= 1000

思路

代码

性能

目标

给你一个二进制字符串 s 和一个整数 k。

在一次操作中，你必须选择恰好 k 个不同的下标，并将每个 '0' 翻转为 '1'，每个 '1' 翻转为 '0'。

返回使字符串中所有字符都等于 '1' 所需的最少操作次数。如果不可能，则返回 -1。

示例 1:

输入： s = "110", k = 1
输出： 1
解释：
s 中有一个 '0'。
由于 k = 1，我们可以直接在一次操作中翻转它。

示例 2:

输入： s = "0101", k = 3
输出： 2
解释：
每次操作选择 k = 3 个下标的一种最优操作方案是：
操作 1：翻转下标 [0, 1, 3]。s 从 "0101" 变为 "1000"。
操作 2：翻转下标 [1, 2, 3]。s 从 "1000" 变为 "1111"。
因此，最少操作次数为 2。

示例 3:

输入： s = "101", k = 2
输出： -1
解释：
由于 k = 2 且 s 中只有一个 '0'，因此不可能通过翻转恰好 k 个位来使所有字符变为 '1'。因此，答案是 -1。

说明:

1 <= s.length <= 10^5
s[i] 的值为 '0' 或 '1'。
1 <= k <= s.length

思路

代码

性能

目标

特殊的二进制字符串是具有以下两个性质的二进制序列：

0 的数量与 1 的数量相等。
二进制序列的每一个前缀码中 1 的数量要大于等于 0 的数量。

给定一个特殊的二进制字符串 s。

一次移动操作包括选择字符串 s 中的两个连续的、非空的、特殊子串，并交换它们。两个字符串是连续的，如果第一个字符串的最后一个字符与第二个字符串的第一个字符的索引相差正好为 1。

返回在字符串上应用任意次操作后可能得到的字典序最大的字符串。

示例 1:

输入: S = "11011000"
输出: "11100100"
解释:
将子串 "10" （在 s[1] 出现） 和 "1100" （在 s[3] 出现）进行交换。
这是在进行若干次操作后按字典序排列最大的结果。

示例 2：

输入：s = "10"
输出："10"

说明：

1 <= s.length <= 50
s[i] 为 '0' 或 '1'。
s 是一个特殊的二进制字符串。

思路

代码

性能

目标

给你一个只包含字符 'a'、'b' 和 'c' 的字符串 s。

如果一个子串中所有不同字符出现的次数都相同，则称该子串为平衡子串。

请返回 s 的最长平衡子串的长度。

子串是字符串中连续的、非空的字符序列。

示例 1：

输入： s = "abbac"
输出： 4
解释：
最长的平衡子串是 "abba"，因为不同字符 'a' 和 'b' 都恰好出现了 2 次。

示例 2：

输入： s = "aabcc"
输出： 3
解释：
最长的平衡子串是 "abc"，因为不同字符 'a'、'b' 和 'c' 都恰好出现了 1 次。

示例 3：

输入： s = "aba"
输出： 2
解释：
最长的平衡子串之一是 "ab"，因为不同字符 'a' 和 'b' 都恰好出现了 1 次。另一个最长的平衡子串是 "ba"。

说明：

1 <= s.length <= 10^5
s 仅包含字符 'a'、'b' 和 'c'。

思路

定义平衡子串是字符出现次数相同的字符串，给定一个由 a b c 三种字符组成的字符串，返回最长的平衡子串长度。

// todo

代码

性能

目标

给你一个整数数组 nums。

如果子数组中不同偶数的数量等于不同奇数的数量，则称该子数组是平衡的。

返回最长平衡子数组的长度。

子数组是数组中连续且非空的一段元素序列。

示例 1:

输入: nums = [2,5,4,3]
输出: 4
解释:
最长平衡子数组是 [2, 5, 4, 3]。
它有 2 个不同的偶数 [2, 4] 和 2 个不同的奇数 [5, 3]。因此，答案是 4 。

示例 2:

输入: nums = [3,2,2,5,4]
输出: 5
解释:
最长平衡子数组是 [3, 2, 2, 5, 4] 。
它有 2 个不同的偶数 [2, 4] 和 2 个不同的奇数 [3, 5]。因此，答案是 5。

示例 3:

输入: nums = [1,2,3,2]
输出: 3
解释:
最长平衡子数组是 [2, 3, 2]。
它有 1 个不同的偶数 [2] 和 1 个不同的奇数 [3]。因此，答案是 3。

说明:

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

提示:

Store the first (or all) occurrences for each value in pos[val].
Build a lazy segment tree over start indices l in [0..n-1] that supports range add and can tell if any index has value 0 (keep mn/mx).
Use sign = +1 for odd values and sign = -1 for even values.
Initialize by adding each value's contribution with update(p, n-1, sign) where p is its current first occurrence.
Slide left l: pop pos[nums[l]], let next = next occurrence or n, do update(0, next-1, -sign), then query for any r >= l with value 0 and update ans = max(ans, r-l+1).

思路

// todo

代码

性能

目标

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

三段式子数组是一个连续子数组 nums[l...r]（满足 0 <= l < r < n），并且存在下标 l < p < q < r，使得：

nums[l...p] 严格递增，
nums[p...q] 严格递减，
nums[q...r] 严格递增。

请你从数组 nums 的所有三段式子数组中找出和最大的那个，并返回其最大和。

示例 1：

输入：nums = [0,-2,-1,-3,0,2,-1]
输出：-4
解释：
选择 l = 1, p = 2, q = 3, r = 5：
nums[l...p] = nums[1...2] = [-2, -1] 严格递增 (-2 < -1)。
nums[p...q] = nums[2...3] = [-1, -3] 严格递减 (-1 > -3)。
nums[q...r] = nums[3...5] = [-3, 0, 2] 严格递增 (-3 < 0 < 2)。
和 = (-2) + (-1) + (-3) + 0 + 2 = -4。

示例 2:

输入: nums = [1,4,2,7]
输出: 14
解释:
选择 l = 0, p = 1, q = 2, r = 3：
nums[l...p] = nums[0...1] = [1, 4] 严格递增 (1 < 4)。
nums[p...q] = nums[1...2] = [4, 2] 严格递减 (4 > 2)。
nums[q...r] = nums[2...3] = [2, 7] 严格递增 (2 < 7)。
和 = 1 + 4 + 2 + 7 = 14。

说明:

4 <= n = nums.length <= 10^5
-10^9 <= nums[i] <= 10^9
保证至少存在一个三段式子数组。

思路

3637.三段式数组I 判断是否是三段式数组，本题则是计算数组的三段式子数组的最大和。

定义 dp[k][i] 表示第 k 段以 i 结尾的前 k 段子数组的最大和，其中 k ∈ [0.2]。由于每一段至少有两个元素，如果 i - 1 是该段的起始，根据前面的定义，应该属于 k - 1 段。因此有 dp[k][i] = Math.max(dp[k - 1][i - 1], dp[k][i - 1]) + nums[i]，当 k = 0 时，将 dp[k - 1][i - 1] 替换为 nums[i - 1] 即可。如果处于严格递增段，可以是第一段或第三段，如果处于严格递减段，则只能是第二段。

代码


/**
 * @date 2026-02-04 8:57
 */
public class MaxSumTrionic3640 {

    public long maxSumTrionic(int[] nums) {
        int n = nums.length;
        long[][] dp = new long[3][n];
        for (int k = 0; k < 3; k++) {
            Arrays.fill(dp[k], Long.MIN_VALUE / 2);
        }
        long res = Long.MIN_VALUE / 2;
        for (int i = 1; i < n; i++) {
            if (nums[i] > nums[i - 1]) {
                dp[0][i] = Math.max(nums[i - 1], dp[0][i - 1]) + nums[i];
                dp[2][i] = Math.max(dp[1][i - 1], dp[2][i - 1]) + nums[i];
            } else if (nums[i] < nums[i - 1]) {
                dp[1][i] = Math.max(dp[0][i - 1], dp[1][i - 1]) + nums[i];
            }
            res = Math.max(res, dp[2][i]);
        }
        return res;
    }

}

性能

3013.将数组分成最小总代价的子数组II

目标

给你一个下标从 0 开始长度为 n 的整数数组 nums 和两个正整数 k 和 dist 。

一个数组的代价是数组中的第一个元素。比方说，[1,2,3] 的代价为 1 ，[3,4,1] 的代价为 3 。

你需要将 nums 分割成 k 个连续且互不相交的子数组，满足第二个子数组与第 k 个子数组中第一个元素的下标距离不超过 dist 。换句话说，如果你将 nums 分割成子数组 nums[0..(i1 - 1)], nums[i1..(i2 - 1)], ..., nums[ik-1..(n - 1)] ，那么它需要满足 ik-1 - i1 <= dist 。

请你返回这些子数组的最小总代价。

示例 1：

输入：nums = [1,3,2,6,4,2], k = 3, dist = 3
输出：5
解释：将数组分割成 3 个子数组的最优方案是：[1,3] ，[2,6,4] 和 [2] 。这是一个合法分割，因为 ik-1 - i1 等于 5 - 2 = 3 ，等于 dist 。总代价为 nums[0] + nums[2] + nums[5] ，也就是 1 + 2 + 2 = 5 。
5 是分割成 3 个子数组的最小总代价。

示例 2：

输入：nums = [10,1,2,2,2,1], k = 4, dist = 3
输出：15
解释：将数组分割成 4 个子数组的最优方案是：[10] ，[1] ，[2] 和 [2,2,1] 。这是一个合法分割，因为 ik-1 - i1 等于 3 - 1 = 2 ，小于 dist 。总代价为 nums[0] + nums[1] + nums[2] + nums[3] ，也就是 10 + 1 + 2 + 2 = 15 。
分割 [10] ，[1] ，[2,2,2] 和 [1] 不是一个合法分割，因为 ik-1 和 i1 的差为 5 - 1 = 4 ，大于 dist 。
15 是分割成 4 个子数组的最小总代价。

示例 3：

输入：nums = [10,8,18,9], k = 3, dist = 1
输出：36
解释：将数组分割成 4 个子数组的最优方案是：[10] ，[8] 和 [18,9] 。这是一个合法分割，因为 ik-1 - i1 等于 2 - 1 = 1 ，等于 dist 。总代价为 nums[0] + nums[1] + nums[2] ，也就是 10 + 8 + 18 = 36 。
分割 [10] ，[8,18] 和 [9] 不是一个合法分割，因为 ik-1 和 i1 的差为 3 - 1 = 2 ，大于 dist 。
36 是分割成 3 个子数组的最小总代价。

说明：

3 <= n <= 10^5
1 <= nums[i] <= 10^9
3 <= k <= n
k - 2 <= dist <= n - 2

思路

定义数组的代价是其第一个元素值，有一个数组 nums，将其分割成 k 个连续且不相交的子数组，并且要求第 2 个子数组与第 k 个子数组的第一个元素的下标的距离不超过 dist，求子数组的最小总代价。

//todo

代码

性能

2977.转换字符串的最小成本II

目标

给你两个下标从 0 开始的字符串 source 和 target ，它们的长度均为 n 并且由小写英文字母组成。

另给你两个下标从 0 开始的字符串数组 original 和 changed ，以及一个整数数组 cost ，其中 cost[i] 代表将字符串 original[i] 更改为字符串 changed[i] 的成本。

你从字符串 source 开始。在一次操作中，如果存在任意下标 j 满足 cost[j] == z 、original[j] == x 以及 changed[j] == y ，你就可以选择字符串中的子串 x 并以 z 的成本将其更改为 y 。你可以执行任意数量的操作，但是任两次操作必须满足以下两个条件之一：

在两次操作中选择的子串分别是 source[a..b] 和 source[c..d] ，满足 b < c 或 d < a 。换句话说，两次操作中选择的下标不相交。
在两次操作中选择的子串分别是 source[a..b] 和 source[c..d] ，满足 a == c 且 b == d 。换句话说，两次操作中选择的下标相同。

返回将字符串 source 转换为字符串 target 所需的最小成本。如果不可能完成转换，则返回 -1 。

注意，可能存在下标 i 、j 使得 original[j] == original[i] 且 changed[j] == changed[i] 。

示例 1：

输入：source = "abcd", target = "acbe", original = ["a","b","c","c","e","d"], changed = ["b","c","b","e","b","e"], cost = [2,5,5,1,2,20]
输出：28
解释：将 "abcd" 转换为 "acbe"，执行以下操作：
- 将子串 source[1..1] 从 "b" 改为 "c" ，成本为 5 。
- 将子串 source[2..2] 从 "c" 改为 "e" ，成本为 1 。
- 将子串 source[2..2] 从 "e" 改为 "b" ，成本为 2 。
- 将子串 source[3..3] 从 "d" 改为 "e" ，成本为 20 。
产生的总成本是 5 + 1 + 2 + 20 = 28 。 
可以证明这是可能的最小成本。

示例 2：

输入：source = "abcdefgh", target = "acdeeghh", original = ["bcd","fgh","thh"], changed = ["cde","thh","ghh"], cost = [1,3,5]
输出：9
解释：将 "abcdefgh" 转换为 "acdeeghh"，执行以下操作：
- 将子串 source[1..3] 从 "bcd" 改为 "cde" ，成本为 1 。
- 将子串 source[5..7] 从 "fgh" 改为 "thh" ，成本为 3 。可以执行此操作，因为下标 [5,7] 与第一次操作选中的下标不相交。
- 将子串 source[5..7] 从 "thh" 改为 "ghh" ，成本为 5 。可以执行此操作，因为下标 [5,7] 与第一次操作选中的下标不相交，且与第二次操作选中的下标相同。
产生的总成本是 1 + 3 + 5 = 9 。
可以证明这是可能的最小成本。

示例 3：

输入：source = "abcdefgh", target = "addddddd", original = ["bcd","defgh"], changed = ["ddd","ddddd"], cost = [100,1578]
输出：-1
解释：无法将 "abcdefgh" 转换为 "addddddd" 。
如果选择子串 source[1..3] 执行第一次操作，以将 "abcdefgh" 改为 "adddefgh" ，你无法选择子串 source[3..7] 执行第二次操作，因为两次操作有一个共用下标 3 。
如果选择子串 source[3..7] 执行第一次操作，以将 "abcdefgh" 改为 "abcddddd" ，你无法选择子串 source[1..3] 执行第二次操作，因为两次操作有一个共用下标 3 。

说明：

1 <= source.length == target.length <= 1000
source、target 均由小写英文字母组成
1 <= cost.length == original.length == changed.length <= 100
1 <= original[i].length == changed[i].length <= source.length
original[i]、changed[i] 均由小写英文字母组成
original[i] != changed[i]
1 <= cost[i] <= 10^6

思路

代码

性能

3651.带传送的最小路径成本

目标

给你一个 m x n 的二维整数数组 grid 和一个整数 k。你从左上角的单元格 (0, 0) 出发，目标是到达右下角的单元格 (m - 1, n - 1)。

有两种移动方式可用：

普通移动：你可以从当前单元格 (i, j) 向右或向下移动，即移动到 (i, j + 1)（右）或 (i + 1, j)（下）。成本为目标单元格的值。
传送：你可以从任意单元格 (i, j) 传送到任意满足 grid[x][y] <= grid[i][j] 的单元格 (x, y)；此移动的成本为 0。你最多可以传送 k 次。

返回从 (0, 0) 到达单元格 (m - 1, n - 1) 的最小总成本。

示例 1:

输入: grid = [[1,3,3],[2,5,4],[4,3,5]], k = 2
输出: 7
解释:
我们最初在 (0, 0)，成本为 0。
当前位置    移动           新位置      总成本
(0, 0)    向下移动        (1, 0)     0 + 2 = 2
(1, 0)    向右移动        (1, 1)     2 + 5 = 7
(1, 1)    传送到(2, 2)    (2, 2)     7 + 0 = 7
到达右下角单元格的最小成本是 7。

示例 2:

输入: grid = [[1,2],[2,3],[3,4]], k = 1
输出: 9
解释:
我们最初在 (0, 0)，成本为 0。
当前位置    移动       新位置     总成本
(0, 0)    向下移动    (1, 0)    0 + 2 = 2
(1, 0)    向右移动    (1, 1)    2 + 3 = 5
(1, 1)    向下移动    (2, 1)    5 + 4 = 9
到达右下角单元格的最小成本是 9。

说明:

2 <= m, n <= 80
m == grid.length
n == grid[i].length
0 <= grid[i][j] <= 10^4
0 <= k <= 10

思路

有一个 m x n 的二维矩阵 grid，可以向右/向下移动，每次移动的成本为目标单元格的值。此外，在任意单元格 (i, j)，可以 零成本 传送到任意满足条件 (grid[x][y] <= grid[i][j]) 的单元格 (x, y)。求从 (0, 0) 出发最多传送 k 次到达 (m - 1, n - 1) 的最小成本。

定义 dp[i][j][t] 表示从 (0, 0) 最多传送 t 次到达 (i - 1, j - 1) 的最小成本。如果不传送，dp[i][j][t] = min(dp[i - 1][j][t], dp[i][j - 1][t]) + grid[i - 1][j - 1]，如果传送，需要找到所有元素值大于等于 grid[i - 1][j - 1] 的单元格 (x, y)，取 dp[x][y][t - 1] 的最小值。

代码


/**
 * @date 2026-01-28 10:04
 */
public class MinCost3651 {

    public int minCost(int[][] grid, int k) {
        int m = grid.length;
        int n = grid[0].length;
        int[][][] dp = new int[m + 1][n + 1][k + 1];
        for (int i = 0; i <= m; i++) {
            for (int j = 0; j <= n; j++) {
                Arrays.fill(dp[i][j], Integer.MAX_VALUE / 2);
            }
        }
        int maxCost = 0;
        for (int[] row : grid) {
            for (int cost : row) {
                maxCost = Math.max(maxCost, cost);
            }
        }
        int[] min = new int[maxCost + 1];
        Arrays.fill(min, Integer.MAX_VALUE);
        int[] suffixMin = new int[maxCost + 2];
        Arrays.fill(suffixMin, Integer.MAX_VALUE);
        for (int t = 0; t <= k; t++) {
            dp[0][1][t] = -grid[0][0];
            dp[1][0][t] = -grid[0][0];
            for (int i = 1; i <= m; i++) {
                for (int j = 1; j <= n; j++) {
                    int cost = grid[i - 1][j - 1];
                    dp[i][j][t] = Math.min(Math.min(dp[i - 1][j][t], dp[i][j - 1][t]) + cost, suffixMin[cost]);
                    min[cost] = Math.min(min[cost], dp[i][j][t]);
                }
            }

            for (int i = maxCost; i >= 0; i--) {
                suffixMin[i] = Math.min(suffixMin[i + 1], min[i]);
            }
        }

        return dp[m][n][k];
    }

}

性能

3510.移除最小数对使数组有序II

目标

给你一个数组 nums，你可以执行以下操作任意次数：

选择相邻元素对中和最小的一对。如果存在多个这样的对，选择最左边的一个。
用它们的和替换这对元素。

返回将数组变为非递减所需的最小操作次数。

如果一个数组中每个元素都大于或等于它前一个元素（如果存在的话），则称该数组为非递减。

示例 1：

输入： nums = [5,2,3,1]
输出： 2
解释：
元素对 (3,1) 的和最小，为 4。替换后 nums = [5,2,4]。
元素对 (2,4) 的和为 6。替换后 nums = [5,6]。
数组 nums 在两次操作后变为非递减。

示例 2：

输入： nums = [1,2,2]
输出： 0
解释：
数组 nums 已经是非递减的。

说明：

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

提示：

We can perform the simulation using data structures.
Maintain an array index and value using a map since we need to find the next and previous ones.
Maintain the indices to be removed using a hash set.
Maintain the neighbor sums with the smaller indices (set or priority queue).
Keep the 3 structures in sync during the removals.

2026 年 6 月
一	二	三	四	五	六	日
1	2	3	4	5	6	7
8	9	10	11	12	13	14
15	16	17	18	19	20	21
22	23	24	25	26	27	28
29	30