十四 贪心
1 贪心算法
1.1 什么是贪心
贪心的本质是选择每一阶段的局部最优，从而达到全局最优。
这么说有点抽象，来举一个例子：
例如，有一堆钞票，你可以拿走十张，如果想达到最大的金额，你要怎么拿？
指定每次拿最大的，最终结果就是拿走最大数额的钱。
每次拿最大的就是局部最优，最后拿走最大数额的钱就是推出全局最优。
再举一个例子如果是 有一堆盒子，你有一个背包体积为n，如何把背包尽可能装满，如果还每次选最大的盒子，就不行了。这时候就需要动态规划。动态规划的问题在下一个系列会详细讲解。
1.2 贪心的套路（什么时候用贪心）
很多同学做贪心的题目的时候，想不出来是贪心，想知道有没有什么套路可以一看就看出来是贪心。
说实话贪心算法并没有固定的套路。
1.3 解题步骤
贪心算法一般分为如下四步：
- 将问题分解为若干个子问题
- 找出适合的贪心策略
- 求解每一个子问题的最优解
- 将局部最优解堆叠成全局最优解
这个四步其实过于理论化了，我们平时在做贪心类的题目时，如果按照这四步去思考，真是有点“鸡肋”。
做题的时候，只要想清楚 局部最优 是什么，如果推导出全局最优，其实就够了
不好意思了，贪心没有套路，说白了就是常识性推导加上举反例。
题目1——买卖股票的最佳时机【83】
给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
示例 1：
输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
示例 2：
输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 没有交易完成, 所以最大利润为 0。
提示：
- 1 <= prices.length <= 105
- 0 <= prices[i] <= 104
思路：想法就是在上涨的段买入和卖出
每次去维护最小值和最大利润
public int maxProfit(int[] nums) {
int maxProfit = Integer.MIN_VALUE, minPrice = nums[0];
for (int num : nums) {
minPrice = Math.min(minPrice, num);
maxProfit = Math.max(maxProfit,num – minPrice);
}
return maxProfit;
}
题目2——跳跃游戏【54】
给你一个非负整数数组 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 ， 所以永远不可能到达最后一个下标。
提示：
- 1 <= nums.length <= 104
- 0 <= nums[i] <= 105
思路：从后向前走看能不能走到
只有当i+nums[i]>=j才能从i走到j
public boolean canJump(int[] nums) {
int n = nums.length;
int j = n – 1;
for (int i = n – 2; i >= 0; i—) {
if (nums[i] + i >= j) {
j = i;
}
}
return j == 0;
}
题目3——跳跃游戏 II【35】
定一个长度为 n 的 0 索引整数数组 nums。初始位置在下标 0。
每个元素 nums[i] 表示从索引 i 向后跳转的最大长度。换句话说，如果你在索引 i 处，你可以跳转到任意 (i + j) 处：
- 0 <= j <= nums[i] 且
- i + j < n
返回到达 n – 1 的最小跳跃次数。测试用例保证可以到达 n – 1。
示例 1:
输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。
示例 2:
输入: nums = [2,3,0,1,4]
输出: 2
提示:
- 1 <= nums.length <= 104
- 0 <= nums[i] <= 1000
- 题目保证可以到达 n – 1
思路：动态规划
dp[i]:到达位置i的最小跳数
public int jump(int[] nums) {
int n = nums.length;
int[] dp = new int[n];
Arrays.fill(dp, Integer.MAX_VALUE);
dp[0] = 0;
for (int i = 0; i < n; i++) {
for (int j = 1; j <= nums[i] && i + j < n; j++) {
dp[i + j] = Math.min(dp[i + j], dp[i] + 1);
}
}
return dp[n – 1];
}
贪心：维护一个一个最远可以到达的位置，
预判跳法，找每一个预备起跳点的最远
/*
* 贪心：一跳一跳的看，维护的的是你跳step次每次能到最远的距离
* */
int n = nums.length;
int maxPos = 0;
int end = 0;
int step = 0;
for (int i = 0; i < n–1; i++) {
maxPos = Math.max(maxPos, nums[i] + i);
if (i == end) {
step++;
end = maxPos;
}
}
return step;
题目4——划分字母区间【22】
给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。例如，字符串 "ababcc" 能够被分为 ["abab", "cc"]，但类似 ["aba", "bcc"] 或 ["ab", "ab", "cc"] 的划分是非法的。
注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s 。
返回一个表示每个字符串片段的长度的列表。
示例 1：
输入：s = "ababcbacadefegdehijhklij"
输出：[9,7,8]
解释：
划分结果为 "ababcbaca"、"defegde"、"hijhklij" 。
每个字母最多出现在一个片段中。
像 "ababcbacadefegde", "hijhklij" 这样的划分是错误的，因为划分的片段数较少。
示例 2：
输入：s = "eccbbbbdec"
输出：[10]
提示：
- 1 <= s.length <= 500
- s 仅由小写英文字母组成
思路：
String有什么定位的函数？
public List<Integer> partitionLabels(String s){
List<Integer> ans = new ArrayList<>();
int end = s.lastIndexOf(s.charAt(0));
int len = 1;
for (int i = 1; i < s.length(); i++) {
if (i <= end) {
end = Math.max(end, s.lastIndexOf(s.charAt(i)));
len++;
} else {
ans.add(len);
len = 1;
end = s.lastIndexOf(s.charAt(i));
}
}
ans.add(len);
return ans;
}
优化：
时间换空间，记录String中最后一个字母
public List<Integer> partitionLabels(String s){
List<Integer> ans = new ArrayList<>();
int[] last = new int[26];
for (int i = 0; i < s.length(); i++) {
last[s.charAt(i) – 'a'] = i;
}
int start = 0, end = 0;
for (int i = 0; i < s.length(); i++) {
end = Math.max(end, last[s.charAt(i)–'a']);
if (end == i) {
ans.add(end – start + 1);
start = end + 1;
}
}
return ans;
}
