贪心的本质是选择每一阶段的局部最优，从而达到全局最优。
贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择，就能得到问题的答案。贪心算法需要充分挖掘题目中条件，没有固定的模式，解决有贪心算法需要一定的直觉和经验。
贪心算法不是对所有问题都能得到整体最优解。能使用贪心算法解决的问题具有「贪心选择性质」。「贪心选择性质」严格意义上需要数学证明。能使用贪心算法解决的问题必须具备「无后效性」，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。
一般数学证明有如下两种方法：
11. 盛最多水的容器
11. 盛最多水的容器
双指针
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
public class Solution {
public int maxArea(int[] height) {
int l = 0, r = height.length - 1;
int ans = 0;
while (l < r) {
int area = Math.min(height[l], height[r]) * (r - l);
ans = Math.max(ans, area);
if (height[l] <= height[r]) {
++l;
}
else {
--r;
}
}
return ans;
}
}
|
55. 跳跃游戏
55. 跳跃游戏
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
public class Solution {
public boolean canJump(int[] nums) {
int n = nums.length;
int rightmost = 0;
for (int i = 0; i < n; ++i) {
if (i <= rightmost) {
rightmost = Math.max(rightmost, i + nums[i]);
if (rightmost >= n - 1) {
return true;
}
}
}
return false;
}
}
|
122. 买卖股票的最佳时机 II
122. 买卖股票的最佳时机 II
1
2
3
4
5
6
7
8
9
10
|
class Solution {
public int maxProfit(int[] prices) {
int ans = 0;
int n = prices.length;
for (int i = 1; i < n; ++i) {
ans += Math.max(0, prices[i] - prices[i - 1]);
}
return ans;
}
}
|