贪心

题目要求 给你一个整数数组 nums。 你一开始站在下标 0。 nums[i] 表示： 从下标 i 最多可以向右跳多少步 题目要求返回： 到达最后一个下标所需的最少跳跃次数 输入输出 输入：nums: List[int] 输出：int 从下标 0 出发 每个数字表示最大跳跃长度，不是必须跳这么远 题目保证一定可以到达最后一个下标 只需要返回最少跳数，不需要返回具体路径 示例 输入：nums = [2,3,1,1,4] 输出：2 一种最少跳法是： 0 -> 1 -> 4 从下标 0 跳到下标 1，再从下标 1 跳到最后一个下标。 输入：nums = [2,3,0,1,4] 输出：2 虽然中间有 0，但仍然可以： 0 -> 1 -> 4 约束 1 <= nums.length <= 10^4 0 <= nums[i] <= 1000 题目保证 nums[n - 1] 可达 Step 1：45 不是问能不能到，而是问最少几步到 如果刚做完 LeetCode 55，已经知道可以维护： ...

题目要求 给你一个区间数组 intervals。 每个区间写成： [start, end] 题目要求删除尽量少的区间，使剩下的区间互不重叠。 最后返回： 最少需要删除多少个区间 输入输出 输入：intervals: List[List[int]] 输出：int 每个区间满足 start < end 如果两个区间只是在端点相接，不算重叠 也就是说： [1,2] 和 [2,3] 可以同时保留。 示例 输入：intervals = [[1,2],[2,3],[3,4],[1,3]] 输出：1 删除 [1,3] 后，剩下： [[1,2],[2,3],[3,4]] 这些区间互不重叠。 再看两个边界例子： 输入：intervals = [[1,2],[1,2],[1,2]] 输出：2 三个完全相同的区间最多只能保留一个，所以要删除两个。 输入：intervals = [[1,2],[2,3]] 输出：0 这两个区间只在端点 2 相接，不算重叠，所以不用删除。 约束 1 <= intervals.length <= 10^5 intervals[i].length == 2 -5 * 10^4 <= start_i < end_i <= 5 * 10^4 Step 1：不要先问删哪个，先问最多能留几个 先看这个例子： intervals = [[1,2],[2,3],[3,4],[1,3]] 题目问的是： ...

题目要求 给你一个气球数组 points。 每个气球是一个水平区间： [start, end] 如果一支箭射在横坐标 x 上，并且： start <= x <= end 那么这支箭可以射爆这个气球。 一支箭会一直向上飞，所以同一个 x 上能覆盖到的所有气球都会被射爆。 题目要求返回： 射爆所有气球需要的最少箭数 输入输出 输入：points: List[List[int]] 输出：int 每个气球是一个区间 [start, end] 箭的位置 x 可以落在端点上 不需要返回每支箭的位置，只需要返回最少箭数 示例 输入：points = [[10,16],[2,8],[1,6],[7,12]] 输出：2 一种射法是： x = 6 射爆 [2,8] 和 [1,6] x = 11 射爆 [10,16] 和 [7,12] 再看两个边界例子： 输入：points = [[1,2],[3,4],[5,6],[7,8]] 输出：4 这些气球互不相交，每个气球都需要一支箭。 输入：points = [[1,2],[2,3],[3,4],[4,5]] 输出：2 因为箭可以射在端点上，所以： x = 2 可以射爆 [1,2] 和 [2,3] x = 4 可以射爆 [3,4] 和 [4,5] 约束 1 <= points.length <= 10^5 points[i].length == 2 -2^31 <= start < end <= 2^31 - 1 Step 1：一支箭到底能覆盖哪些气球？ 先看一个很小的问题： ...

题目要求 给你一个数组 prices，其中 prices[i] 表示第 i 天的股票价格。 你只能完成一次交易： 选择某一天买入一支股票 选择未来某一天卖出这支股票 返回能获得的最大利润。如果无法盈利，返回 0。 输入输出 输入：prices: List[int] 输出：最大利润 int 只能买一次、卖一次。 买入日必须早于卖出日。 可以选择不交易，此时利润是 0。 示例 输入：prices = [7,1,5,3,6,4] 输出：5 最优做法是在价格为 1 时买入，在价格为 6 时卖出，利润是 6 - 1 = 5。 输入：prices = [7,6,4,3,1] 输出：0 价格一直下降，任何买入后再卖出都会亏钱，所以返回 0。 约束 1 <= prices.length <= 10^5 0 <= prices[i] <= 10^4 Step 1：先固定买卖顺序 先看这个例子： prices = [7,1,5,3,6,4] 如果只看价格差，最大利润来自： 1 -> 6 profit = 5 这是合法的，因为价格 1 出现在价格 6 之前。 ...

题目要求 给你一个整数数组 nums。 你一开始站在下标 0。nums[i] 表示从位置 i 最多可以向右跳多少步。 题目要求判断：能不能到达最后一个下标。 输入输出 输入：nums: List[int] 输出：bool 从下标 0 出发。 每个位置的数字表示最大跳跃长度，不是必须跳这么远。 只需要判断能否到达最后一个下标，不需要返回具体路径。 示例 输入：nums = [2,3,1,1,4] 输出：true 一种跳法是： 0 -> 1 -> 4 从下标 0 可以跳到下标 1，再从下标 1 跳到最后一个下标。 输入：nums = [3,2,1,0,4] 输出：false 无论怎么跳，都会被下标 3 的 0 卡住，无法到达最后一个下标 4。 约束 1 <= nums.length <= 10^4 0 <= nums[i] <= 10^5 Step 1：不要先猜路径，先看覆盖范围 先看失败样例： nums = [3,2,1,0,4] 从下标 0 最多可以跳到下标 3。 看起来选择很多： 0 -> 1 0 -> 2 0 -> 3 当前 baseline 是： ...