算法题-31，32

给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。

示例 1：
输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。
示例 2：
输入：nums = [3,2,1,0,4]
输出：false
解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。

这道题也是一道经典的贪心算法，站在下标0每个位置nums[i]表示：从i最多可以往右跳nums[i]步，然后能不能达到最后一个位置。我们不需要真的跳，而是去维护一个变量记录当前能达到的最远位置。

核心思考就是，我们当前位置的下标是否大于我们维护的那个变量，如果下标大说明这个位置个根本到不了，如果小于我们维护的这个变量就更新最远的距离

具体的代码实现

/** * @param {number[]} nums * @return {boolean} */ var canJump = function(nums) { let maxReach = 0 for(let i = 0;i < nums.length;i++){ if(i > maxReach)return false maxReach = Math.max(maxReach,i + nums[i]) } return true };

我们分析一下两个示例

[2,3,1,1,4]

[3,2,1,0,4]

我们在每次遍历都在选择当前位置能到达的最大距离，所以是贪心。

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：

每行的元素从左到右升序排列。
每列的元素从上到下升序排列。

我拿到这一道题第一反应是使用二分法，对每一行二分，但是时间复杂度是O(m log n)，突然发先右上角的元素有神奇的性质，它左边都比它小，它下面都比它大，这意味着一次比较就能排除一整行或一整列。

假设从：
row = 0
col = n - 1 // 右上角
开始。
每一步：
如果：matrix[row][col] === target，找到，返回 true
如果：matrix[row][col] > target，说明：这一列都比 target 大，往左走，col--
如果：matrix[row][col] < target，说明：这一行都比 target 小，往下走，row++

var searchMatrix = function(matrix, target) { const m = matrix.length const n = matrix[0].length let row = 0 let col = n - 1 while (row < m && col >= 0) { const val = matrix[row][col] if (val === target) return true if (val > target) { col-- } else { row++ } } return false };

时间复杂度，每一步：不是往下，就是往左，最多：m + n 步，所以：时间复杂度 O(m + n)