力扣45. 跳跃游戏 II

2023-12-24 05:49:19

贪心算法

  • 思路:
    • 在 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;
    }
};

文章来源:https://blog.csdn.net/N_BenBird/article/details/135176707
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。