LeetCode 1871. 跳跃游戏 VII（贪心）

示例 1：
输入：s = "011010", minJump = 2, maxJump = 3
输出：true
解释：
第一步，从下标 0 移动到下标 3 。
第二步，从下标 3 移动到下标 5 。

示例 2：
输入：s = "01101110", minJump = 2, maxJump = 3
输出：false
 
提示：
2 <= s.length <= 10^5
s[i] 要么是 '0' ，要么是 '1'
s[0] == '0'
1 <= minJump <= maxJump < s.length

class Solution {
public:
    bool canReach(string s, int minJump, int maxJump) {
        if(s.back() == '1')
            return false;
        int n = s.size(), end = 0;//最远可到达的位置 end
        vector<bool> vis(n, false);
        vis[0] = true;
        for(int i = 0; i < n && i <= end; i++)
        {
            if(!vis[i]) continue;
            int p1 = i+minJump;
            int p2 = min(n-1, i+maxJump);
            for(int j = max(p1, end+1); j <= p2; ++j)//max保证每个位置只检查1次
            {
                if(s[j] == '0')
                {
                    vis[j] = true;
                    if(j == n-1)//走到最后了
                        return true;
                }
            }
            end = p2;//更新end位置
        }
        return false;
    }
};