力扣45. 跳跃游戏 II

贪心算法

• 思路：
  • 在 pos 位置，能跳到 pos + nums[pos] 位置；
  • 正向遍历数组，迭代出能跳到的最大位置：

    • maxPos = std::max(maxPos, idx + nums[idx]);

  • 在遍历到最大位置的地方则更新步数，并重新统计基于此位置能跳到的最大位置；

class Solution {
public:
    int jump(vector<int>& nums) {
        int maxPos = 0;
        int size = nums.size();
        int step = 0;
        int end = 0;

        for (int idx = 0; idx < size - 1; ++idx) {
            if (maxPos >= idx) {
                maxPos = std::max(maxPos, idx + nums[idx]);
                if (idx == end) {
                    end = maxPos;
                    ++step;
                }
            }
        }

        return step;
    }
};