标签： medium

2414.最长的字母序连续子字符串的长度

目标

字母序连续字符串 是由字母表中连续字母组成的字符串。换句话说，字符串 "abcdefghijklmnopqrstuvwxyz" 的任意子字符串都是 字母序连续字符串 。

  • 例如，"abc" 是一个字母序连续字符串，而 "acb" 和 "za" 不是。

给你一个仅由小写英文字母组成的字符串 s ，返回其 最长 的 字母序连续子字符串 的长度。

示例 1：

输入：s = "abacaba"
输出：2
解释：共有 4 个不同的字母序连续子字符串 "a"、"b"、"c" 和 "ab" 。
"ab" 是最长的字母序连续子字符串。

示例 2：

输入：s = "abcde"
输出：5
解释："abcde" 是最长的字母序连续子字符串。

说明：

  • 1 <= s.length <= 10^5
  • s 由小写英文字母组成

思路

首先要明确 字母序连续 的含义， abc 是字母序连续，abd abccd 是不是字母序连续？不是。

An alphabetical continuous string is a string consisting of consecutive letters in the alphabet. In other words, it is any substring of the string "abcdefghijklmnopqrstuvwxyz".

字母序连续字符串是由字母表中连续的字母组成的字符串，即 abcdefghijklmnopqrstuvwxyz 的任意子字符串。

有一个由小写英文字母组成的字符串，求它的字母序连续子串的最大长度。显然，最大长度不会超过26。只需要一次遍历，如果不是字母序连续则重新计数，取最大值即可。

代码


/**
 * @date 2024-09-19 13:48
 */
public class LongestContinuousSubstring2414 {

    public int longestContinuousSubstring(String s) {
        int n = s.length();
        int res = 0;
        int cnt = 0;
        int last = s.charAt(0) - 1;
        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            if (c - last == 1) {
                res = Math.max(res, ++cnt);
            } else {
                cnt = 1;
            }
            last = c;
        }
        return res;
    }

}

性能

2332.坐上公交的最晚时间

目标

给你一个下标从 0 开始长度为 n 的整数数组 buses ，其中 buses[i] 表示第 i 辆公交车的出发时间。同时给你一个下标从 0 开始长度为 m 的整数数组 passengers ，其中 passengers[j] 表示第 j 位乘客的到达时间。所有公交车出发的时间互不相同，所有乘客到达的时间也互不相同。

给你一个整数 capacity ，表示每辆公交车 最多 能容纳的乘客数目。

每位乘客都会搭乘下一辆有座位的公交车。如果你在 y 时刻到达，公交在 x 时刻出发，满足 y <= x 且公交没有满，那么你可以搭乘这一辆公交。最早 到达的乘客优先上车。

返回你可以搭乘公交车的最晚到达公交站时间。你 不能 跟别的乘客同时刻到达。

注意：数组 buses 和 passengers 不一定是有序的。

示例 1：

输入：buses = [10,20], passengers = [2,17,18,19], capacity = 2
输出：16
解释：
第 1 辆公交车载着第 1 位乘客。
第 2 辆公交车载着你和第 2 位乘客。
注意你不能跟其他乘客同一时间到达，所以你必须在第二位乘客之前到达。

示例 2：

输入：buses = [20,30,10], passengers = [19,13,26,4,25,11,21], capacity = 2
输出：20
解释：
第 1 辆公交车载着第 4 位乘客。
第 2 辆公交车载着第 6 位和第 2 位乘客。
第 3 辆公交车载着第 1 位乘客和你。

说明：

  • n == buses.length
  • m == passengers.length
  • 1 <= n, m, capacity <= 10^5
  • 2 <= buses[i], passengers[i] <= 10^9
  • buses 中的元素 互不相同 。
  • passengers 中的元素 互不相同 。

思路

已知某路公交车的最大容量 capacity，离开时间数组 buses，以及乘客到达时间数组 passengers。离开/到达 时间是整数，乘客的到达时间各不相同，自己的到达时间也不能与其它乘客重复，问能够赶上公交的最晚到达时间。

刚开始想到了二分查找，理论上来说只要在 0 ~ buses[n - 1] 内找到不与 passengers 重复的最大值即可。但是问题在于，如果与其它乘客的到达时间重复了，我们该如何缩小范围呢？向左找还是向右找？这个是不确定的，二分查找需要能够明确地排除一半的数据范围，这里是做不到的。

我们也不能直接从小于 buses[n - 1] 的乘客开始向前枚举，因为车的容量是有限的，如果前面积压的乘客过多，后面的乘客照样上不了车。

如果没有限制条件，我们只需要作为最后一班车的最后一名乘客上车即可。但这里要求到达时间不能与其它乘客相同，如果已经有乘客在最后一班车准备离开时到达，我们无法作为最后一名乘客上车。考虑这种极端情况，公交到达时间为 5 10 15 容量为5，乘客到达时间为 2 3 4 5 6 | 7 8 9 10 11 | 12 13 14 15 16 我们必须在时间 1 之前到达，其它时间会与乘客到达时间相同或者赶不上公交。

我们可以首先将公交的离开时间以及乘客的到达时间排序，然后枚举每一辆公交，如果 passengers[i] <= buses[j] && capacity > 0 就可以上车，并将 capacity-- 。车满了或者没有剩余乘客在当前公交离开时间之前到达，将 capacity 重置，等待下一班车。然后我们判断最后一班车是否有剩余位置，如果有则取 buses[n - 1]，否则取最后一位上车的乘客到达时间。最后判断是否与最后一名上车的乘客的到达时间相同，如果相同，则将时间减一并与倒数第二名上车的乘客到达时间比较，以此类推。最开始使用了哈希表保存了乘客的到达时间，然后判断是否在集合内，其实没有必要，因为乘客到达时间数组已经排过序了，依次从后向前找如果不相等则一定不在数组中。

最后的处理有许多细节，比如不能直接取最后一名乘客的到达时间减1，需要判断是否有空位；如果有空位不能直接返回buses[n - 1]，需要判断是否重复；最开始是外层枚举乘客，内层枚举公交车，这样会漏掉乘客枚举完但还剩余公交车的情况，这时最后一名乘客不能算入最后一班车的位置，等等。

代码


/**
 * @date 2024-09-18 10:41
 */
public class LatestTimeCatchTheBus2332 {

    public int latestTimeCatchTheBus_v2(int[] buses, int[] passengers, int capacity) {
        Arrays.sort(buses);
        Arrays.sort(passengers);
        int n = buses.length;
        int m = passengers.length;
        int i = 0, j = 0, cnt = capacity;
        for (; i < n; i++) {
            cnt = capacity;
            while (cnt > 0 && j < m && passengers[j] <= buses[i]) {
                cnt--;
                j++;
            }
        }
        int res;
        j--;
        if (cnt > 0) {
            res = buses[n - 1];
        } else {
            res = passengers[j];
        }
        while (j >= 0 && passengers[j] == res) {
            res--;
            j--;
        }
        return res;
    }

}

性能

2390.从字符串中移除星号

目标

给你一个包含若干星号 * 的字符串 s 。

在一步操作中，你可以：

  • 选中 s 中的一个星号。
  • 移除星号 左侧 最近的那个 非星号 字符，并移除该星号自身。

返回移除 所有 星号之后的字符串。

注意：

  • 生成的输入保证总是可以执行题面中描述的操作。
  • 可以证明结果字符串是唯一的。

示例 1：

输入：s = "leet**cod*e"
输出："lecoe"
解释：从左到右执行移除操作：
- 距离第 1 个星号最近的字符是 "leet**cod*e" 中的 't' ，s 变为 "lee*cod*e" 。
- 距离第 2 个星号最近的字符是 "lee*cod*e" 中的 'e' ，s 变为 "lecod*e" 。
- 距离第 3 个星号最近的字符是 "lecod*e" 中的 'd' ，s 变为 "lecoe" 。
不存在其他星号，返回 "lecoe" 。

示例 2：

输入：s = "erase*****"
输出：""
解释：整个字符串都会被移除，所以返回空字符串。

说明：

  • 1 <= s.length <= 10^5
  • s 由小写英文字母和星号 * 组成
  • s 可以执行上述操作

思路

移除字符串中的星号以及星号左侧的非星号字符。

直接模拟栈的行为即可，可以使用StringBuilder，遇到星号就删除最后一个字符。

deleteCharAt(index) 实际上调用的是 System.arraycopy(value, index+1, value, index, count-index-1); 将index后的数据前移了一位。这里删除的是最后一个字符，实际上就是将指针向前移了一位。那我们可以直接将指针向前移，省去这一系列的函数调用。

可以直接原地修改，定义一个指针 p 与 i 同步增长，如果遇到 *， 指针 p 回退，否则将下标 i 对应的值写入当前 p 指向的位置。

代码


/**
 * @date 2024-09-14 8:56
 */
public class RemoveStars2390 {

    public String removeStars_v2(String s) {
        char[] chars = s.toCharArray();
        int n = chars.length;
        int p = 0;
        for (int i = 0; i < n; i++) {
            if (chars[i] == '*') {
                p--;
            } else {
                chars[p++] = chars[i];
            }
        }
        return new String(chars, 0, p);
    }

}

性能

2576.求出最多标记下标

目标

给你一个下标从 0 开始的整数数组 nums 。

一开始，所有下标都没有被标记。你可以执行以下操作任意次：

  • 选择两个 互不相同且未标记 的下标 i 和 j ，满足 2 * nums[i] <= nums[j] ，标记下标 i 和 j 。

请你执行上述操作任意次，返回 nums 中最多可以标记的下标数目。

示例 1：

输入：nums = [3,5,2,4]
输出：2
解释：第一次操作中，选择 i = 2 和 j = 1 ，操作可以执行的原因是 2 * nums[2] <= nums[1] ，标记下标 2 和 1 。
没有其他更多可执行的操作，所以答案为 2 。

示例 2：

输入：nums = [9,2,5,4]
输出：4
解释：第一次操作中，选择 i = 3 和 j = 0 ，操作可以执行的原因是 2 * nums[3] <= nums[0] ，标记下标 3 和 0 。
第二次操作中，选择 i = 1 和 j = 2 ，操作可以执行的原因是 2 * nums[1] <= nums[2] ，标记下标 1 和 2 。
没有其他更多可执行的操作，所以答案为 4 。

示例 3：

输入：nums = [7,6,8]
输出：0
解释：没有任何可以执行的操作，所以答案为 0 。

说明：

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

提示：

  • Think about how to check that performing k operations is possible.
  • To perform k operations, it’s optimal to use the smallest k elements and the largest k elements and think about how to match them.
  • It’s optimal to match the ith smallest number with the k-i + 1 largest number.
  • Now we need to binary search on the answer and find the greatest possible valid k.

思路

有一个数组 nums，每一次操作我们可以标记数组中未被标记的两个数，要求其中一个数的两倍小于等于另一个数。问经过任意次操作，最多可以标记多少个数。

题目与下标无关，可以先排序。使用双指针 l r 从前往后找到第一个大于等于其两倍的数 p。然后 l+1 r 继续向后搜索，直到 l 到达 p，这时将 l 赋值为 r，并且赋值 r = r + 1，继续前面的算法。 应该使用一个数组记录是否已标记，当 l 第一次到达 p 时，应跳转到之前 r 未被标记的下标。

这种贪心策略也是不对的，对于示例2，排序后的数组为 2 4 5 9。如果优先标记 2 4 后面就不能再标记了，而如果先标记 2 5 我们还可以标记 4 9。

那如果我们倒过来考虑呢？从后往前找试试。反过来也不对，例如 10 10 40 100 如果先标记 40 100 前面就不能再标记了。

这样一来我们不知道满足条件后是否应该标记，需要搜索解空间看看哪个最大。回溯搜索相当于搜索n叉树 O(n^n)，如果不进行剪枝或者记忆的话肯定超时。如果考虑动态规划，状态又比较多，取决于元素是否被标记。

看了提示，匹配策略一定是前 k 个小的 small[i] 与后 k 个大的 big[i] 匹配。还是上面的例子 2 4 | 5 9 10 10 | 40 100 最优的匹配方式就是 2 5 4 9 10 40 10 100。现在问题就变成了找出最大的 k。使用二分法查找满足条件的最大 k，然后返回 2k 就是答案。

这道题卡住的点是没想清楚匹配方式。先入为主地以滑动窗口的方式匹配，连续地比较，匹配第一个能够匹配的，这种策略是不对的。

更优的解法是直接用双指针遍历，因为二分查找的判断复杂度为O(k)，整体是O(klogn)，不如双指针的O(n)。

代码


/**
 * @date 2024-09-12 9:14
 */
public class MaxNumOfMarkedIndices2576 {

    /**
     * 排序的复杂度O(nlogn) 双指针匹配的复杂度O((n + 1) / 2)
     */
    public int maxNumOfMarkedIndices_v1(int[] nums) {
        int n = nums.length;
        Arrays.sort(nums);
        int rs = (n + 1) / 2;
        int l = 0;
        for (int r = rs; r < n; r++) {
            if (nums[l] * 2 <= nums[r]) {
                l++;
            }
        }
        return 2 * l;
    }

    /**
     * 排序的复杂度O(nlogn) 二分查找复杂度O(klogn) 其中判断的复杂度O(k) k最坏的情况下取n/2
     */
    public int maxNumOfMarkedIndices(int[] nums) {
        int n = nums.length;
        Arrays.sort(nums);
        int l = 0, r = n / 2, k = l + (r - l) / 2;
        while (l <= r) {
            if (check(nums, k)) {
                l = k + 1;
            } else {
                r = k - 1;
            }
            k = l + (r - l) / 2;
        }
        return 2 * r;
    }

    public boolean check(int[] nums, int k) {
        int n = nums.length;
        for (int i = 0; i < k; i++) {
            if (nums[i] * 2 > nums[n - k + i]) {
                return false;
            }
        }
        return true;
    }

}

性能

二分查找

双指针

2555.两个线段获得的最多奖品

目标

在 X轴 上有一些奖品。给你一个整数数组 prizePositions ，它按照 非递减 顺序排列，其中 prizePositions[i] 是第 i 件奖品的位置。数轴上一个位置可能会有多件奖品。再给你一个整数 k 。

你可以选择两个端点为整数的线段。每个线段的长度都必须是 k 。你可以获得位置在任一线段上的所有奖品（包括线段的两个端点）。注意，两个线段可能会有相交。

  • 比方说 k = 2 ，你可以选择线段 [1, 3] 和 [2, 4] ，你可以获得满足 1 <= prizePositions[i] <= 3 或者 2 <= prizePositions[i] <= 4 的所有奖品 i 。

请你返回在选择两个最优线段的前提下，可以获得的 最多 奖品数目。

示例 1：

输入：prizePositions = [1,1,2,2,3,3,5], k = 2
输出：7
解释：这个例子中，你可以选择线段 [1, 3] 和 [3, 5] ，获得 7 个奖品。

示例 2：

输入：prizePositions = [1,2,3,4], k = 0
输出：2
解释：这个例子中，一个选择是选择线段 [3, 3] 和 [4, 4] ，获得 2 个奖品。

说明：

  • 1 <= prizePositions.length <= 10^5
  • 1 <= prizePositions[i] <= 10^9
  • 0 <= k <= 10^9
  • prizePositions 有序非递减。

思路

x轴的一些整数坐标上放有奖品，相同坐标点上可能有多个奖品。已知所有奖品所在坐标从小到大排序后的数组 prizePositions，问使用两个长度为k的线段最多能覆盖多少个奖品。线段可以相交，但相交区间内的奖品仅计数一次，线段端点处的奖品也计入总数。

最直观的想法是使用滑动窗口，固定区间长度，然后求能够覆盖的最多奖品数。但我们需要的是两个线段所能覆盖的最多奖品，能否记录下第一次求得的区间范围，然后在范围之外（两个线段尽量不相交才能覆盖更多奖品）在用相同的方法求次最多的奖品数。这看上去似乎可行，但具体写完之后会发现一些问题。

  • 如果存在多个最大区间如何处理？可以参考下图，k取3的情况，不同的选择直接影响另一线段的取值。可以用一个列表记录区间范围，然后分别对这些区间范围之外的区间执行同样的算法？时间复杂度为 O(m * l)，m 为最大线段个数，l 为区间长度。

  • 就算上面的复杂度可以接受，两个线段获得最多奖品，一定要其中一个线段覆盖最多的奖品吗？这个是不必要的。参考下图，k取2的情况：

针对这道题，这种贪心策略是不行的，局部最优解并不一定是全局最优解。现在我们没有一个明确的目标，最优的线段该如何取？如果我们同时滑动两个窗口呢？暴力写法是先固定一个，然后滑动另一个。时间复杂度为 O(n^2)，肯定超时。我们发现这里面有重复的子问题，定义 num[i] 表示以 prizePositions[i] 为起点长度为 k 的线段所能覆盖的奖品数。然后再用一个 max[i] 表示起点大于等于 prizePositions[i] 长度为 k 的线段所能覆盖的最大奖品数。这样我们就能以 O(1) 的复杂度取到固定一个窗口之后，另一个窗口的最大值。枚举固定窗口求出最大值即可。

写完之后发现，保存 num[i] 是不必要的，它只用来更新当前的 max[i]。

滑动窗口有两种写法，枚举左边界，循环内部直接到达可能的最右边界。另一种写法是枚举右边界，如果条件不满足，更新左边界直到满足条件。注意确保不要越界。

官网题解提供了二分法的解法，确实遇到有序数组就要想到二分法，但是这里二分找什么呢？大概是二分找所能覆盖的左边界，然后还是动态规划求不超过左边界的另一线段所能覆盖的最大值。官方题解这个解法的java版本好像是其它题目的，给错答案了。

代码


/**
 * @date 2024-09-11 8:57
 */
public class MaximizeWin2555 {

    public int maximizeWin_v1(int[] prizePositions, int k) {
        int n = prizePositions.length;
        if (k * 2 + 1 >= prizePositions[n - 1] - prizePositions[0]) {
            return n;
        }
        int res = 1;
        int[] max = new int[n + 1];
        int l = n - 1;
        for (int r = n - 1; r >= 0; r--) {
            while (l >= 0 && prizePositions[r] - prizePositions[l] <= k) {
                max[l] = Math.max(r - l + 1, max[l + 1]);
                res = Math.max(res, r - l + 1 + max[r + 1]);
                l--;
            }
        }
        return res;
    }

}

性能

2181.合并零之间的节点

目标

给你一个链表的头节点 head ，该链表包含由 0 分隔开的一连串整数。链表的 开端 和 末尾 的节点都满足 Node.val == 0 。

对于每两个相邻的 0 ，请你将它们之间的所有节点合并成一个节点，其值是所有已合并节点的值之和。然后将所有 0 移除，修改后的链表不应该含有任何 0 。

返回修改后链表的头节点 head 。

示例 1：

输入：head = [0,3,1,0,4,5,2,0]
输出：[4,11]
解释：
上图表示输入的链表。修改后的链表包含：
- 标记为绿色的节点之和：3 + 1 = 4
- 标记为红色的节点之和：4 + 5 + 2 = 11

示例 2：

输入：head = [0,1,0,3,0,2,2,0]
输出：[1,3,4]
解释：
上图表示输入的链表。修改后的链表包含：
- 标记为绿色的节点之和：1 = 1
- 标记为红色的节点之和：3 = 3
- 标记为黄色的节点之和：2 + 2 = 4

说明：

  • 列表中的节点数目在范围 [3, 2 * 10^5] 内
  • 0 <= Node.val <= 1000
  • 不 存在连续两个 Node.val == 0 的节点
  • 链表的 开端 和 末尾 节点都满足 Node.val == 0

思路

将链表中由零分隔的节点合并为一个节点（将它们的值相加），然后删除零节点。链表头与尾为零，中间节点也可能为零。

使用栈保存非零节点，如果栈非空并且当前节点值为零，则合并栈中节点，并将其值赋值给前面的零节点，然后将最后一个非零节点的 next 赋值给前面零节点的 next。

其实也没必要用栈保存，直接累加到前面零节点的值上即可。

代码


/**
 * @date 2024-09-09 9:09
 */
public class MergeNodes2181 {

    public ListNode mergeNodes_v2(ListNode head) {
        // 用于操作head中的零节点，初始化为空节点，第一次修改并没有实际修改链表中的节点值
        ListNode zeroNode = new ListNode();
        ListNode res = head;
        while (head.next != null) {
            if (head.val == 0) {
                // 上一个零节点的next指向当前零节点
                zeroNode.next = head;
                // 指向当前零节点
                zeroNode = head;
            } else {
                zeroNode.val += head.val;
            }
            head = head.next;
        }
        zeroNode.next = null;
        return res;
    }

}

性能

3176.求出最长好子序列I

目标

给你一个整数数组 nums 和一个 非负 整数 k 。如果一个整数序列 seq 满足在范围下标范围 [0, seq.length - 2] 中存在 不超过 k 个下标 i 满足 seq[i] != seq[i + 1] ，那么我们称这个整数序列为 好 序列。

请你返回 nums 中 好 子序列 的最长长度

示例 1：

输入：nums = [1,2,1,1,3], k = 2
输出：4
解释：
最长好子序列为 [1,2,1,1] 。

示例 2：

输入：nums = [1,2,3,4,5,1], k = 0
输出：2
解释：
最长好子序列为 [1,1] 。

说明：

  • 1 <= nums.length <= 500
  • 1 <= nums[i] <= 10^9
  • 0 <= k <= min(nums.length, 25)

提示：

  • The absolute values in nums don’t really matter. So we can remap the set of values to the range [0, n - 1].
  • Let dp[i][j] be the length of the longest subsequence till index j with at most i positions such that seq[i] != seq[i + 1].
  • For each value x from left to right, update dp[i][x] = max(dp[i][x] + 1, dp[i - 1][y] + 1), where y != x.

思路

求整数数组 nums 的子序列，要求子序列中最多存在 k 个下标 i 满足 seq[i] != seq[i + 1]，即至多 k 对相邻元素 不同。

只要选出了子序列，那么相邻元素 不同 的对数就已经确定。

记忆化搜索超时了 // todo

代码

性能

2860.让所有学生保持开心的分组方法数

目标

给你一个下标从 0 开始、长度为 n 的整数数组 nums ，其中 n 是班级中学生的总数。班主任希望能够在让所有学生保持开心的情况下选出一组学生：

如果能够满足下述两个条件之一，则认为第 i 位学生将会保持开心：

  • 这位学生被选中，并且被选中的学生人数 严格大于 nums[i] 。
  • 这位学生没有被选中，并且被选中的学生人数 严格小于 nums[i] 。

返回能够满足让所有学生保持开心的分组方法的数目。

示例 1：

输入：nums = [1,1]
输出：2
解释：
有两种可行的方法：
班主任没有选中学生。
班主任选中所有学生形成一组。 
如果班主任仅选中一个学生来完成分组，那么两个学生都无法保持开心。因此，仅存在两种可行的方法。

示例 2：

输入：nums = [6,0,3,3,6,7,2,7]
输出：3
解释：
存在三种可行的方法：
班主任选中下标为 1 的学生形成一组。
班主任选中下标为 1、2、3、6 的学生形成一组。
班主任选中所有学生形成一组。

说明：

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

思路

从数组中选择一组元素，使之满足该组元素个数严格大于组中所有元素值并且严格小于未被选择的元素值，求满足条件的所有选择数。

注意到元素值不超过数组长度，可以先统计各元素值的出现次数 cnt[i]，然后遍历 cnt。

这道题的关键是要意识到：值相同的元素要么同时被选，要么同时不被选。因为选择的元素个数 sum 应该大于所有选择的元素值，小于所有未选择的元素值，一个元素不可能既小于 sum 又大于 sum。题目的本质是将学生成两组（被选择的和未被选择的），选择的标准是根据所选人数动态变化的，水平相同的学生要么都选，要么都不选，要一碗水端平，这就是题目名想要表达的处世哲学吧。

  • 当 cnt[0] == 0 时，说明所有元素都大于0，因此可以一个都不选。
  • 当 cnt[i] != 0 时，如果我们想要选择这些元素值为i的学生，需要满足选择后的学生总数 sum 大于 i，并且 cnt[i+1] ~ cnt[sum] 应该都为0，否则就存在小于 sum 但是未被选的学生了。

官网题解使用的是排序，满足 sorted[i - 1] < i && i < sorted[i] 时累加计数。不过排序的复杂度是O(nlogn)，其实我们的计数数组也是有序的，算是计数排序吧，时间复杂度为O(n)。

代码


/**
 * @date 2024-09-04 10:29
 */
public class CountWays2860 {
    public int countWays(List<Integer> nums) {
        int n = nums.size();
        int[] cnt = new int[n];
        for (Integer num : nums) {
            cnt[num]++;
        }
        int[] prefix = new int[n];
        for (int i = 1; i < n; i++) {
            prefix[i] = prefix[i - 1] + cnt[i];
        }
        int res = cnt[0] > 0 ? 0 : 1;
        int sum = 0;
        for (int i = 0; i < n; i++) {
            sum += cnt[i];
            if (sum > i && cnt[i] != 0 && prefix[Math.min(n - 1, sum)] == prefix[i]) {
                res++;
            }
        }
        return res;
    }
}

性能

2708.一个小组的最大实力值

目标

给你一个下标从 0 开始的整数数组 nums ，它表示一个班级中所有学生在一次考试中的成绩。老师想选出一部分同学组成一个 非空 小组，且这个小组的 实力值 最大，如果这个小组里的学生下标为 i0, i1, i2, ... , ik ，那么这个小组的实力值定义为 nums[i0] * nums[i1] * nums[i2] * ... * nums[ik​] 。

请你返回老师创建的小组能得到的最大实力值为多少。

示例 1：

输入：nums = [3,-1,-5,2,5,-9]
输出：1350
解释：一种构成最大实力值小组的方案是选择下标为 [0,2,3,4,5] 的学生。实力值为 3 * (-5) * 2 * 5 * (-9) = 1350 ，这是可以得到的最大实力值。

示例 2：

输入：nums = [-4,-5,-4]
输出：20
解释：选择下标为 [0, 1] 的学生。得到的实力值为 20 。我们没法得到更大的实力值。

说明：

  • 1 <= nums.length <= 13
  • -9 <= nums[i] <= 9

思路

有一个存在负数的数组，求它的非空子序列使得子序列的乘积最大。

首先，要选择所有正数，不能选零（除非全是零），负数必须成对的选（可以使用栈来保存）。可以将数组从小到大排序，从后向前取所有大于零的值，然后再从前向后取，判断栈是否为空，为空入栈，非空出栈，直到零。特别需要注意的是初值的设置需要分情况讨论，如果全是零或者至多一个负数，直接返回零。如果至少有一个正数，则初值设为1。如果全是负数，初值设为第一个元素，之所以不设为1是因为如果只有一个负数，那么就应该取这个值，如果设为1后面再配对的话就不对了，所以需要特殊处理成对匹配的情况。

代码


/**
 * @date 2024-09-03 8:57
 */
public class MaxStrength2708 {

    public long maxStrength(int[] nums) {
        long res = 1L;
        Arrays.sort(nums);
        int n = nums.length;
        int i = n - 1;
        for (; i >= 0; i--) {
            if (nums[i] > 0) {
                res *= nums[i];
            } else if (nums[i] < 0) {
                // 跳过0，使i指向最后一个负数
                break;
            }
        }
        int j = 0;
        boolean flag = true;
        // 至多一个负数，其余全是0，返回0。
        if (i <= 0 && nums[n - 1] == 0) {
            return 0L;
        } else if (i == n - 1) {
            // 如果全是负数
            res = nums[0];
            flag = false;
            j = 1;
        }
        ArrayDeque<Integer> stack = new ArrayDeque<>();
        for (; j <= i; j++) {
            if (nums[j] < 0) {
                if (stack.isEmpty() && flag) {
                    stack.push(nums[j]);
                } else {
                    if (!flag) {
                        res *= nums[j];
                    } else {
                        res *= stack.pop() * nums[j];
                    }
                    flag = true;
                }
            }
        }
        return res;
    }

}

性能

2024.考试的最大困扰度

目标

一位老师正在出一场由 n 道判断题构成的考试，每道题的答案为 true （用 'T' 表示）或者 false （用 'F' 表示）。老师想增加学生对自己做出答案的不确定性，方法是 最大化 有 连续相同 结果的题数。（也就是连续出现 true 或者连续出现 false）。

给你一个字符串 answerKey ，其中 answerKey[i] 是第 i 个问题的正确结果。除此以外，还给你一个整数 k ，表示你能进行以下操作的最多次数：

  • 每次操作中，将问题的正确答案改为 'T' 或者 'F' （也就是将 answerKey[i] 改为 'T' 或者 'F' ）。

请你返回在不超过 k 次操作的情况下，最大 连续 'T' 或者 'F' 的数目。

示例 1：

输入：answerKey = "TTFF", k = 2
输出：4
解释：我们可以将两个 'F' 都变为 'T' ，得到 answerKey = "TTTT" 。
总共有四个连续的 'T' 。

示例 2：

输入：answerKey = "TFFT", k = 1
输出：3
解释：我们可以将最前面的 'T' 换成 'F' ，得到 answerKey = "FFFT" 。
或者，我们可以将第二个 'T' 换成 'F' ，得到 answerKey = "TFFF" 。
两种情况下，都有三个连续的 'F' 。

示例 3：

输入：answerKey = "TTFTTFTT", k = 1
输出：5
解释：我们可以将第一个 'F' 换成 'T' ，得到 answerKey = "TTTTTFTT" 。
或者我们可以将第二个 'F' 换成 'T' ，得到 answerKey = "TTFTTTTT" 。
两种情况下，都有五个连续的 'T' 。

说明：

  • n == answerKey.length
  • 1 <= n <= 5 * 10^4
  • answerKey[i] 要么是 'T' ，要么是 'F'
  • 1 <= k <= n

思路

有一个字符串 answerKey 由 T 或 F 组成, 允许我们执行 k 次操作，每次操作可以将字符串中的 T 改为 F 或者 F 改为 T。问 T 或 F 可能的最大连续个数。

这道题没有做出来，想着使用动态规划去做，但是没有找到合适的状态定义。比如 dp[i][j][k] 表示 [0,i] 以 T 或 F 结尾剩余操作次数 k 时的最大连续个数。2 x 10^8 的存储空间肯定不行。

题解说是滑动窗口、或者 前缀和 + 二分查找，也有使用动态规划的。

这道题的难点在于想明白这 k 次操作必须统一，要么全部从 T 改为 F，要么全部从 F 改为 T，才能使连续个数最大。因为如果 T 的连续个数最多，并且存在将 T 改为 F 的操作，那么我们总可以撤回该操作，并将一个 F 改为 T（如果存在的话，如果不存在说明全是T，撤销操作也会加一） 使得连续个数至少加一。

网友题解中的动态规划是这样定义的 dp[i] 表示 [0,i] 中以 answerKey[i] 结尾的连续后缀个数。这里的前提就是遇到不连续的统一从 T 改为 F 或者 从 F 改为 T 使之连续，如果超过了可操作的次数，需要撤回最早的操作，使得当前后缀连续。后缀连续个数可以用当前下标减去最早进行操作的下标计算得到（使用链表保存操作的下标，获取链表head记录的下标后将其删，再将当前下标加入链表末尾）。在计算dp过程中记录其最大值即为最大连续个数。如果对这个动态规划进行存储优化，那就是滑动窗口。

寻找一个窗口，使得窗口内的 T 或者 F 个数小于等于 k，并且使 F 或者 T 的个数最大。滑动窗口的套路一般是枚举右边界，如果条件不满足，更新左边界直到条件满足。

二分的做法本质也是滑动窗口，枚举左边界，二分查找能够到达的最远右边界。

代码


/**
 * @date 2024-09-02 16:55
 */
public class MaxConsecutiveAnswers2024 {

    /**
     * 前缀和 + 二分查找
     * 其实本质也是滑动窗口，枚举左边界，二分查找最远的右边界
     * O(nlogn) 62ms
     */
    public int maxConsecutiveAnswers_v1(String answerKey, int k) {
        int n = answerKey.length();
        int[] prefix = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            if (answerKey.charAt(i - 1) == 'T') {
                prefix[i] = prefix[i - 1] + 1;
            } else {
                prefix[i] = prefix[i - 1];
            }
        }
        int res = 0;
        for (int i = 1; i <= n; i++) {
            int l = i, r = n;
            int mid = l + (r - l) / 2;
            while (l <= r) {
                int num = mid - i + 1;
                int cnt = prefix[mid] - prefix[i - 1];
                if (num - cnt <= k || cnt <= k) {
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }
                mid = l + (r - l) / 2;
            }
            res = Math.max(res, r - i + 1);
        }
        return res;
    }

    /**
     * 滑动窗口 O(n)
     * 21ms
     */
    public int maxConsecutiveAnswers(String answerKey, int k) {
        return Math.max(process(answerKey, k, 'T'), process(answerKey, k, 'F'));
    }

    public int process(String answerKey, int k, char turnTo) {
        int n = answerKey.length();
        int res = 0;
        List<Integer> optsIndex = new LinkedList<>();
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            if (answerKey.charAt(i) != turnTo) {
                if (k > 0) {
                    k--;
                    optsIndex.add(i);
                    cnt++;
                } else {
                    cnt = i - optsIndex.remove(0);
                    optsIndex.add(i);
                }
            } else {
                cnt++;
            }
            res = Math.max(res, cnt);
        }
        return res;
    }

}

性能