跳转至

45. 跳跃游戏 II#

问题描述#

给定一个非负整数数组，你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

你的目标是使用最少的跳跃次数到达数组的最后一个位置。

示例:

输入: [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
     从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。

说明:

假设你总是可以到达数组的最后一个位置。

解题思路#

方法一（超时）#

用 \(\texttt{dis}[i]\) 表示到达位置 \(i\) 的最小步数。

从位置 \(i\) 出发，可以到达的位置范围为 \([i+1,i+\texttt{nums}[i]]\)，步数为 \(\texttt{dis}[i]+1\)，然后我们遍历从每个位置出发能够到达所有位置，然后更新 \(\texttt{dis}[i]\) 即可。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
    def jump(self, nums: List[int]) -> int:
        n = len(nums)
        dis = [n] * n
        dis[0] = 0

        for i in range(n):
            for j in range(i + 1, 1 + min(n - 1, i + nums[i])):
                dis[j] = min(dis[j], dis[i] + 1)

        return dis[-1]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
public:
    int jump(vector<int>& nums) {
        int n = nums.size();
        vector<int> dis(n, n);

        dis[0] = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j <= min(n - 1, i + nums[i]); ++j) {
                dis[j] = min(dis[j], dis[i] + 1);
            }
        }

        return dis[n - 1];
    }
};

实际测试最后一个数据超时，\(n=25,000\) 左右。

时间复杂度：\(\mathcal{O}(n^2)\)
空间复杂度：\(\mathcal{O}(n)\)

方法二（通过）#

容易知道到达位置 \(i-1\) 的最小步数不会大于到达位置 \(i\) 的最小步数，即 \(\texttt{dis}[i-1]\le\texttt{dis}[i]\)。

所以如果在从位置 \(i\) 出发到达的位置 \([i+1,i+\texttt{nums}[i]]\) 中，如果有位置被 \(i\) 位置之前的位置到达了，那么从位置 \(i\) 出发，就可以直接从前面所能到达的位置之后开始遍历。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    def jump(self, nums: List[int]) -> int:
        n = len(nums)
        dis = [n] * n
        dis[0] = 0
        pre = 0 # 保存之前位置能够到达的最远位置

        for i in range(n):
            for j in range(max(pre + 1, i + 1), 1 + min(n - 1, i + nums[i])):
                dis[j] = min(dis[j], dis[i] + 1)
            pre = max(pre, i + nums[i])
        return dis[-1]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int jump(vector<int>& nums) {
        int n = nums.size();
        vector<int> dis(n, n);
        int pre = 0; // 保存之前位置能够到达的最远位置

        dis[0] = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = max(pre + 1, i + 1); j <= min(n - 1, i + nums[i]); ++j) {
                dis[j] = min(dis[j], dis[i] + 1);
            }
            pre = max(pre, i + nums[i]);
        }

        return dis[n - 1];
    }
};

时间复杂度：\(\mathcal{O}(n)\)
空间复杂度：\(\mathcal{O}(n)\)

在上面的分析中，在位置遍历到第一次到达的最远位置时，步数才会发生更新，并且最远位置也更新。

比如说，从位置 \(0\) 出发，能够到达的最远位置为 \(s_1=\texttt{nums}[0]\)，那么到达 \([1,s_1]\) 的最小步数都是 \(1\)，假设从 \([1,s_1]\) 出发能够到达的最远位置为 \(s_2\)，那么到达 \([s_1+1,s_2]\) 的最小步数都是 \(2\)。依次类推。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    def jump(self, nums: List[int]) -> int:
        n = len(nums)
        ans = pre = nxt = 0

        for i in range(n):
            if i == pre + 1:
                ans += 1
                pre = nxt
            nxt = max(nxt, i + nums[i])

        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
public:
    int jump(vector<int>& nums) {
        int n = nums.size();
        int ans = 0, pre = 0, next = 0;

        for (int i = 0; i < n; ++i) {
            if (i == pre + 1) {
                ++ans;
                pre = next;
            }
            next = max(next, i + nums[i]);
        }

        return ans;
    }
};

时间复杂度：\(\mathcal{O}(n)\)
空间复杂度：\(\mathcal{O}(1)\)

返回顶部

在手机上阅读