如果一个正整数每一个数位都是 互不相同 的，我们称它是 特殊整数 。
给你一个 正 整数 n ，请你返回区间 [1, n] 之间特殊整数的数目。
示例 1：
输入：n = 20
输出：19
解释：1 到 20 之间所有整数除了 11 以外都是特殊整数。所以总共有 19 个特殊整数。示例 2：
输入：n = 5
输出：5
解释：1 到 5 所有整数都是特殊整数。示例 3：
输入：n = 135
输出：110
解释：从 1 到 135 总共有 110 个整数是特殊整数。
不特殊的部分数字为：22 ，114 和 131 。说明：
求 1 ~ n 之间的特殊整数，所谓特殊整数指 十进制 下的每一位都不相同的整数。
// todo
字母序连续字符串 是由字母表中连续字母组成的字符串。换句话说，字符串 "abcdefghijklmnopqrstuvwxyz" 的任意子字符串都是 字母序连续字符串 。
给你一个仅由小写英文字母组成的字符串 s ，返回其 最长 的 字母序连续子字符串 的长度。
示例 1：
输入：s = "abacaba"
输出：2
解释：共有 4 个不同的字母序连续子字符串 "a"、"b"、"c" 和 "ab" 。
"ab" 是最长的字母序连续子字符串。示例 2：
输入：s = "abcde"
输出：5
解释："abcde" 是最长的字母序连续子字符串。说明：
首先要明确 字母序连续 的含义， 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;
}
}
给你一个下标从 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 位乘客和你。说明：
已知某路公交车的最大容量 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;
}
}
给你一个数组 routes ，表示一系列公交线路，其中每个 routes[i] 表示一条公交线路，第 i 辆公交车将会在上面循环行驶。
现在从 source 车站出发（初始时不在公交车上），要前往 target 车站。 期间仅可乘坐公交车。
求出 最少乘坐的公交车数量 。如果不可能到达终点车站，返回 -1 。
示例 1：
输入：routes = [[1,2,7],[3,6,7]], source = 1, target = 6
输出：2
解释：最优策略是先乘坐第一辆公交车到达车站 7 , 然后换乘第二辆公交车到车站 6 。示例 2：
输入：routes = [[7,12],[4,5,15],[6],[15,19],[9,12,13]], source = 15, target = 12
输出：-1说明：
0 <= routes[i][j] < 10^6求不带权的最短路径直接使用BFS即可，但这题求的是换乘次数最少的路径。我们可以将问题转化为带权的最短路径问题，如果需要换乘，将权重设为1，否则权重为0。
// todo
环形公交路线上有 n 个站，按次序从 0 到 n - 1 进行编号。我们已知每一对相邻公交站之间的距离，distance[i] 表示编号为 i 的车站和编号为 (i + 1) % n 的车站之间的距离。
环线上的公交车都可以按顺时针和逆时针的方向行驶。
返回乘客从出发点 start 到目的地 destination 之间的最短距离。
示例 1：
输入：distance = [1,2,3,4], start = 0, destination = 1
输出：1
解释：公交站 0 和 1 之间的距离是 1 或 9，最小值是 1。示例 2：
输入：distance = [1,2,3,4], start = 0, destination = 2
输出：3
解释：公交站 0 和 2 之间的距离是 3 或 7，最小值是 3。示例 3：
输入：distance = [1,2,3,4], start = 0, destination = 3
输出：4
解释：公交站 0 和 3 之间的距离是 6 或 4，最小值是 4。说明：
有一个数组 distance，元素 distance[i] 表示车站 i 到 车站 i + 1 的距离。环线上的车可以顺时针或逆时针行驶，求 start 到 destination 的最短距离。
假设，start <= destination。实际上是比较子数组 [start, destination - 1] 的元素和 与 子数组 [0, start - 1] [destination, n - 1] 的元素和，取其中的较小值。
由于是环形的，因此有可能 start > destination。注意处理初始条件，否则子数组 [start, destination - 1] 不合法，而 [0, start - 1] [destination, n - 1] 则覆盖了所有站点。
/**
* @date 2024-09-16 20:08
*/
public class DistanceBetweenBusStops1184 {
public int distanceBetweenBusStops(int[] distance, int start, int destination) {
int n = distance.length;
int s = Math.min(start, destination);
int e = Math.max(start, destination);
int d1 = 0, d2 = 0;
for (int i = 0; i < n; i++) {
if (i < s || i >= e) {
d1 += distance[i];
} else {
d2 += distance[i];
}
}
return Math.min(d1, d2);
}
}
给你一个下标从 0 开始的二维整数数组 nums 表示汽车停放在数轴上的坐标。对于任意下标 i，nums[i] = [starti, endi] ，其中 starti 是第 i 辆车的起点，endi 是第 i 辆车的终点。
返回数轴上被车 任意部分 覆盖的整数点的数目。
示例 1：
输入：nums = [[3,6],[1,5],[4,7]]
输出：7
解释：从 1 到 7 的所有点都至少与一辆车相交，因此答案为 7 。示例 2：
输入：nums = [[1,3],[5,8]]
输出：7
解释：1、2、3、5、6、7、8 共计 7 个点满足至少与一辆车相交，因此答案为 7 。说明：
用一个二维数组表示 n 个线段，每一行表示线段的两个端点，问这些线段覆盖的整数点个数。
简单的想法是将线段覆盖的每个整数加入 HashSet，最后返回集合大小即可。线段个数最多 100 个，端点的范围在 1 ~ 100 最多10000 次循环，可行。
更好的做法是将相交的线段合并，最终仅计算相交线段的长度之和即可。先将线段按照起点排序，如果后面线段的起点小于前面的终点，取当前线段的终点与前面合并线段的终点中的较大值，否则计算长度并累加。
还想到了之前有一道题使用了 差分思想，那个是给定一个整数，判断覆盖该整数的线段有多少个。它是将 cnt[start]++; cnt[end + 1]--，直接累加 [0, query] 内的 cnt[i] 即为答案。
差分数组 diff 的核心思想是记录相邻元素的差，当对连续区间 [i, j] 同时增加 k，可以简化为 diff[i] + k; diff[j + 1] - k。原数组的第 i 个元素可以通过累加差分数组得到。
刚开始理解差分数组可能会想不明白，为什么只修改差分数组两个端点的值就可以将区间内的值同时加 k。核心点是理解当前值是由差分数组累加得来的，从 i 开始，当前值加了 k，后面的差分值为0，因此值与 i 位置相同。当到达 j + 1 减去了 k，后面再累加就不会受到前面的影响。
针对这道题，将原数组视为每个整数点被覆盖的次数，开始时均为 0，差分数组也均为 0。最后只需统计覆盖次数大于 0 的整数个数即可。
/**
* @date 2024-09-15 21:53
*/
public class NumberOfPoints2848 {
/**
* 差分数组 1ms O(n)
*/
public int numberOfPoints_v2(List<List<Integer>> nums) {
// 数据范围为 1~100，0~100 共101个数，但是由于需要访问 end+1，因此初始化为102个
int[] diff = new int[102];
for (List<Integer> segment : nums) {
diff[segment.get(0)]++;
diff[segment.get(1) + 1]--;
}
int res = 0;
int cnt = 0;
for (int i : diff) {
cnt += i;
if (cnt > 0){
res++;
}
}
return res;
}
/**
* 合并区间 排序 O(nlogn) 3ms
*/
public int numberOfPoints_v1(List<List<Integer>> nums) {
PriorityQueue<int[]> q = new PriorityQueue<>((a, b) -> a[0] - b[0]);
for (List<Integer> num : nums) {
q.offer(new int[]{num.get(0), num.get(1)});
}
// 初始化为-1，是因为循环中第一次 res += maxEnd - start + 1; start maxEnd并不是实际的线段数据
int res = -1;
int start = 0;
int maxEnd = 0;
while (!q.isEmpty()) {
int[] segment = q.poll();
int s = segment[0];
int e = segment[1];
if (s > maxEnd) {
res += maxEnd - start + 1;
start = s;
maxEnd = e;
} else {
maxEnd = Math.max(maxEnd, e);
}
}
// 如果最后一个线段无需合并，那么需要单独将其长度加进来
// 如果最后一个线段需要合并，由于队列中没有数据了，也需要将最后合并的线段长度加进来
res += maxEnd - start + 1;
return res;
}
/**
* 5ms O(c*n) c为区间最大长度
*/
public int numberOfPoints(List<List<Integer>> nums) {
Set<Integer> s = new HashSet<>(nums.size());
for (List<Integer> num : nums) {
for (int i = num.get(0); i <= num.get(1); i++) {
s.add(i);
}
}
return s.size();
}
}
给你一个包含若干星号 * 的字符串 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*****"
输出：""
解释：整个字符串都会被移除，所以返回空字符串。说明：
移除字符串中的星号以及星号左侧的非星号字符。
直接模拟栈的行为即可，可以使用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);
}
}
你有 n 个机器人，给你两个下标从 0 开始的整数数组 chargeTimes 和 runningCosts ，两者长度都为 n 。第 i 个机器人充电时间为 chargeTimes[i] 单位时间，花费 runningCosts[i] 单位时间运行。再给你一个整数 budget 。
运行 k 个机器人 总开销 是 max(chargeTimes) + k * sum(runningCosts) ，其中 max(chargeTimes) 是这 k 个机器人中最大充电时间，sum(runningCosts) 是这 k 个机器人的运行时间之和。
请你返回在 不超过 budget 的前提下，你 最多 可以 连续 运行的机器人数目为多少。
示例 1：
输入：chargeTimes = [3,6,1,3,4], runningCosts = [2,1,3,4,5], budget = 25
输出：3
解释：
可以在 budget 以内运行所有单个机器人或者连续运行 2 个机器人。
选择前 3 个机器人，可以得到答案最大值 3 。总开销是 max(3,6,1) + 3 * sum(2,1,3) = 6 + 3 * 6 = 24 ，小于 25 。
可以看出无法在 budget 以内连续运行超过 3 个机器人，所以我们返回 3 。示例 2：
输入：chargeTimes = [11,12,19], runningCosts = [10,8,7], budget = 19
输出：0
解释：即使运行任何一个单个机器人，还是会超出 budget，所以我们返回 0 。说明：
选择连续的 k 个机器人，使开销不超过预算 budget。其中机器人的开销等于其中 所选机器人的最长的充电时间 + k * 所选k个机器人花费之和。
直接的想法是二分查找 k，然后使用滑动窗口记录最小的开销 min，如果 min < budget 增大 k，否则减小 k。时间复杂度为 O(nlogn)。
核心点在于滑动窗口的时候 max(chargeTimes) 如何更新。今天又解锁了新词条：单调队列。
// todo
给你一个下标从 0 开始的整数数组 nums 。
一开始，所有下标都没有被标记。你可以执行以下操作任意次：
请你执行上述操作任意次，返回 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 。说明：
提示：
有一个数组 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;
}
}
二分查找
双指针
在 X轴 上有一些奖品。给你一个整数数组 prizePositions ，它按照 非递减 顺序排列，其中 prizePositions[i] 是第 i 件奖品的位置。数轴上一个位置可能会有多件奖品。再给你一个整数 k 。
你可以选择两个端点为整数的线段。每个线段的长度都必须是 k 。你可以获得位置在任一线段上的所有奖品（包括线段的两个端点）。注意，两个线段可能会有相交。
请你返回在选择两个最优线段的前提下，可以获得的 最多 奖品数目。
示例 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 个奖品。说明：
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;
}
}
