algo/frequency-interview/jump-game-summary/

[giscus[bot]]

algo/frequency-interview/jump-game-summary/

Info 数据结构精品课 (https://labuladong.online/algo/ds-class/) 和 递归算法专题课 (https://labuladong.online/algo/tree-class/) 限时附赠网站会员；算法可视化编辑器上线，点击体验 (https://labuladong.online/algo-visualize...

https://labuladong.github.io/algo/frequency-interview/jump-game-summary/

[littlesquirrel2017]

对贪心算法解法增加了一个提前退出判断, if (end >= n - 1) break, 提交后有提速.

int jump(vector<int>& nums) {
        int n = nums.size();
        int farest = 0;
        int end = 0;
        int jump_cnt = 0;
        for (int i=0; i < n - 1; i++) {
            farest = std::max(farest, i + nums[i]);
            if (end == i) {
                jump_cnt++;
                end = farest;
            }
            if (end >= n - 1) {
                break;
            }
        }
        return jump_cnt;
    }