题目列表
| 题目名称 | 难度 |
|---|---|
| 11. 盛最多水的容器 | Medium |
| 435. 无重叠区间 | Medium |
| 455. 分发饼干 | Easy |
| 55. 跳跃游戏 | Medium |
盛最多水的容器
题目链接：https://leetcode-cn.com/problems/container-with-most-water/
思路：此题使用双指针碰撞和贪心思想，总是贪心先固定容器的宽度。根据木桶原理（盛水的高度由最短的那块木板决定），高的那块木板往里面走，只可能让盛水越来越少，但是短板往里面走，却有可能让盛水越来越多。
我认为写的比较好的题解是这篇。
代码：
class Solution {
public int maxArea(int[] height) {
int length = height.length;
int left = 0, right = length - 1;
int res = 0;
while(left < right){
int area = Math.min(height[left], height[right]) * (right - left);
res = Math.max(res, area);
if(height[left] < height[right]){
left++;
}else{
right--;
}
}
return res;
}
}435. 无重叠区间
题目链接：https://leetcode-cn.com/problems/non-overlapping-intervals/
思路：题目要找到需要移除区间的最小数量，使剩余区间互不重叠，我们可以理解为找到最多的无重叠区间。
对于贪心算法中的区间问题，我们通常会考虑将区间按照右端点进行一个排序。此题也是如此，每个区间的结尾很重要，结尾越小，则后面越有可能容纳更多的区间。
代码：
class Solution {
public int eraseOverlapIntervals(int[][] intervals) {
int length = intervals.length;
if(length < 2){
return 0;
}
Arrays.sort(intervals, Comparator.comparingInt(a -> a[1]));
int res = 0;
int end = intervals[0][1];
for(int i = 1; i < length; ++i){
if(intervals[i][0] < end){
res++;
}else{
end = intervals[i][1];
}
}
return res;
}
}455. 分发饼干
题目链接：https://leetcode-cn.com/problems/assign-cookies/
思路：对于一个孩子来说，如果小的饼干可以满足，我们就没必要用更大的饼干，这样更大的就可以留给其他对饼干大小需求更大的孩子。另一方面，对饼干大小需求小的孩子更容易被满足，所以，我们可以从需求小的孩子开始分配饼干。因为满足一个需求大的孩子跟满足一个需求小的孩子，对我们期望值的贡献是一样的。
我们每次从剩下的孩子中，找出对饼干大小需求最小的，然后发给他剩下的饼干中能满足他的最小的饼干，这就是典型的贪心算法，而这样得到的分配方案，也就是满足的孩子个数最多的方案。
代码：
class Solution {
public int findContentChildren(int[] g, int[] s) {
if(g.length == 0 || s.length == 0){
return 0;
}
Arrays.sort(g);
Arrays.sort(s);
int i = 0, j = 0;
int res = 0;
while(i < g.length && j < s.length){
if(g[i] <= s[j]){
res++;
i++;
j++;
}else{
j++;
}
}
return res;
}
}55. 跳跃游戏
题目链接：https://leetcode-cn.com/problems/jump-game/
从前向后
其实这题最好的解法不是 DP，而是贪婪算法 Greedy Algorithm。
因为我们并不关心每一个位置上的剩余步数，我们只希望知道能否到达末尾，也就是说我们只对最远能到达的位置感兴趣。
维护一个变量
reach，表示最远能到达的位置，初始化为0。遍历数组中每一个数字，如果当前坐标大于
reach或者reach已经抵达最后一个位置则跳出循环，否则就更新 reach 的值为其和i + nums[i]中的较大值，其中i + nums[i]表示当前位置能到达的最大位置。
解题思路：
如果某一个作为起跳点的格子可以跳跃的距离是 3，那么表示后面 3 个格子都可以作为起跳点；
可以对每一个能作为起跳点的格子都尝试跳一次，把能跳到最远的距离不断更新；
如果可以一直跳到最后，就成功了。
代码：
class Solution {
public boolean canJump(int[] nums) {
int maxReach = 0;
for(int i = 0; i < nums.length; i++){
if(i > maxReach){
return false;
}
maxReach = Math.max(maxReach, i + nums[i]);
}
return true;
}
}参考：
