題鏈接：https://leetcode-cn.com/problems/jump-game/
題描述：
解題思路：
對于位置 i 上的元素，它可以跳躍到的最遠位置為 i + nums[i]，如果某個元素跳躍的最遠位置超出或等于陣列末尾的位置則回傳 true，
即，我們依次遍歷陣列元素，并實時維護一個最遠位置，對于當前遍歷元素，如果該元素在最遠位置內，則代表該元素是可到達的，
代碼實作：
/**
* @param {number[]} nums
* @return {boolean}
*/
var canJump = function(nums) {
if (nums.length == 1) {
return true;
}
let maxStep;
maxStep = nums[0];
for (let i = 1; i < nums.length; i++) {
if (maxStep >= nums.length - 1) {
return true;
}
if (i <= maxStep && i + nums[i] > maxStep) {
maxStep = i + nums[i];
}
}
return false;
};
時間復雜度：O(n)
空間復雜度：O(1)
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/231503.html
標籤：其他