贪心算法

买卖股票的最佳时机

https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/

核心思路

如果假设今日买入，未来最高点是未知的，需要遍历后续数组，所以时间复杂度变成n^2；
那么如果假设今日卖出，遍历到此处时历史最低价是已知晓的信息，就降低了时间复杂度，只需要遍历一遍并记录实时最小值和实时最大利润即可；

示例代码

class Solution {public int maxProfit(int[] prices) {int min = 10010;int max = 0;for(int num : prices){if(num<min) min = num;if(max < num - min)max = num - min;}return max;}
}

跳跃游戏

https://leetcode.cn/problems/jump-game/

核心思路

倒序 可达性分析

示例代码

class Solution {public boolean canJump(int[] nums) {//i表示可到达的下标int i = nums.length - 1;//j表示需要确定的下标//若倒二可到达倒一，则计算倒三是否可以到达倒二，否则计算到三是否可以到达倒一；for (int j = nums.length - 2; j >= 0; j--) {if (nums[j] >= i - j) {i = j;}}//若i==0，代表可到达if (i == 0) return true;return false;}
}

跳跃游戏II

https://leetcode.cn/problems/jump-game-ii/

返回到达 nums[n - 1] 的最小跳跃次数

核心思路

贪心策略：在当前位置所能跳到的区间内，找下一次能跳到更远的位置。

示例代码

class Solution {public int jump(int[] nums) {int p = nums.length - 1;//每一步的开始int start = 0;int cnt = 0;while (start < p) {int end = -1;//在start位置，[s,e]闭区间即能跳到的的范围int s = start + 1;int e = start + nums[start];//e没跳到最后的话，就找一下：跳到区间的哪个位置可以下一次跳的更远if (e < p) {for (int i = s; i <= e && i <= p; i++) {if (end <= i + nums[i]) {end = i + nums[i];start = i;}}}else{cnt++;break;}cnt++;}return cnt;}
}

划分字母区间

https://leetcode.cn/problems/partition-labels/

核心思路

本质是合并区间:

​ 遍历，记录下每个字母最后出现的下标；
​ 再次遍历，合并区间，计算长度

示例代码

class Solution {public List<Integer> partitionLabels(String S) {char[] s = S.toCharArray();int n = s.length;int[] last = new int[26];for (int i = 0; i < n; i++) {last[s[i] - 'a'] = i; // 每个字母最后出现的下标}List<Integer> ans = new ArrayList<>();int start = 0, end = 0;for (int i = 0; i < n; i++) {end = Math.max(end, last[s[i] - 'a']); // 更新当前区间 右端点的最大值if (end == i) { // 当前区间合并完毕ans.add(end - start + 1); // 区间长度加入答案start = i + 1; // 下一个区间的左端点}}return ans;}
}