题目描述
LeetCode 1871 — 跳跃游戏 VII (Medium)
给定一个下标从 0 开始的二进制字符串 s 和两个整数 minJump、maxJump。最初，你位于下标 0，且 s[0] == '0'。
当你位于下标 i 时，可以跳到下标 j，需同时满足：
i + minJump <= j <= min(i + maxJump, s.length - 1)s[j] == '0'
请判断能否到达下标 s.length - 1。能则返回 true，否则返回 false。
示例 1：
- 输入：
s = "011010", minJump = 2, maxJump = 3 - 输出：
true - 解释：从 0 跳到 3，再从 3 跳到 5（终点）。
示例 2：
- 输入：
s = "01101110", minJump = 2, maxJump = 3 - 输出：
false - 解释：从 0 能跳到 3；从 3 向右只能到 5 和 6，但 s[5] = '1' 且 s[6] = '1'，无法继续。到不了终点 7。
约束：
2 <= s.length <= 10^5s[i]为'0'或'1's[0] == '0'1 <= minJump <= maxJump < s.length
核心思路
朴素 BFS 的问题
题意很自然地导向 BFS——从下标 0 出发，每次将 [i+minJump, i+maxJump] 范围内的合法 '0' 位置入队，直到到达终点或队列为空。
但直接实现的代价很高。考虑最坏情况：
s = "00000...000"（全 0），minJump = 1, maxJump = n-1
- 下标 0 出队，扫描范围
[1, n-1]，全部 n-1 个位置入队 → O(n) - 下标 1 出队，扫描范围
[2, n-1]，全部 n-2 个位置——但都已访问，白扫 → O(n) - 下标 2 出队，扫描范围
[3, n-1]，n-3 个位置又白扫 → O(n)
每个节点出队都 O(n)，总时间 O(n²)。n = 10^5 时，约 50 亿次操作，必然超时。
根本问题：每次出队，我们都在重复扫描已经被前序节点覆盖过的区间。
滑动窗口优化
观察一个关键性质：跳转方向只有向前（j >= i + minJump），BFS 处理的节点下标天然递增。这意味着一件事——
下标 i 出队时，
[0, i+maxJump]的左侧区间已经被前面的节点"扫过"了。我们唯一需要关心的，是从「上次扫到的位置 + 1」到i+maxJump这一段新区间。
这正是滑动窗口的思路：维护一个指针 furthest，表示已探索到的最远下标。对每个出队节点 i：
- 扫描起点 =
max(i + minJump, furthest + 1)（跳过已探索区域） - 扫描终点 =
min(i + maxJump, n - 1)
furthest 单向递增，数组中每个下标最多被检查一次。总扫描次数从 O(n²) 降为 O(n)。
解法：BFS + 滑动窗口
bool canReach(string s, int minJump, int maxJump) {
int n = s.length();
// 终点如果是 '1'，不可能到达
if (s[n - 1] == '1') return false;
queue<int> q;
q.push(0);
// furthest：已扫描到的最远下标（滑动窗口右边界）
int furthest = 0;
while (!q.empty()) {
int i = q.front();
q.pop();
// 滑动窗口：只扫描区间内的未探索部分
int left = max(i + minJump, furthest + 1);
int right = min(i + maxJump, n - 1);
for (int j = left; j <= right; j++) {
if (s[j] == '0') {
if (j == n - 1) return true;
q.push(j);
}
}
// 窗口右边界向前滑动
furthest = max(furthest, right);
}
return false;
}
复杂度： 时间 O(n)，空间 O(n)。每个下标最多入队一次、被 for 循环检查一次。