1 答疑
1.1 什么是贪心算法的”左最优”与”右最优”
“左最优”和”右最优”是贪心算法中的两种策略：
-
左最优 (Leftmost Greedy): 在每一步选择中，总是选择最左边（最早出现的）可行的选项。
-
右最优 (Rightmost Greedy): 在每一步选择中，总是选择最右边（最晚出现的）可行的选项。
这两种策略是贪心算法中根据具体问题选择的不同方向。
1.2 这两种最优问题，分别用什么方法解决？
一般左最优可以采取边遍历边找出”当前的最值”， 右最优不能向左最优一样通过左到右的遍历稍带最值，所以一般需要预处理从右到左遍历并且将得到的最值存放到数组中。
2 “左最优” 类题目
左最优其实也是一种局部最优
2.1 字节笔试题
小明在玩一场通关游戏，初始血量为1，关卡有怪兽或者有血包（正数就是血包可回血数，负数说明是怪兽的伤害值），当捡到血包时会加血量，碰到怪兽时会掉血，现在指定初始血量为x，关卡是一个数组，小明必须按照数组的顺序玩游戏，当碰到一个怪兽时，他可以选择将这个怪兽扔到数组末尾，小明可以无限次地将怪兽移到数组末尾,问小明最少移动几次就能存活,如果无论怎么移动都不能存活则返回-1， 假设关卡是这样的[-200,-300,400]，则返回-1，假如是这样的[200,100,-250,-60,-70,100]，则返回1，只需要把-250挪到尾部，
思路：当发现自己血量不足时，就从当前已经遍历过的所有关卡中，选择耗费血量最多的那个关卡并且放到最后一关，如果即使这样挪开了耗血量最大的一关自身血量还是为负，则直接返回-1，说明无法通关
———————————————— 版权声明：本文为CSDN博主「xxx_520s」的原创文章，遵循CC 4.0
BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/yxg520s/article/details/131989933
2.2 leetcode 1642. 可以到达的最远建筑
这样的贪心思路，871题最低加油次数和630课程表III也有体现。
两种贪心策略均可：
优先使用梯子，梯子不够时选取差值最小的出堆改用砖头。(小根堆)
优先使用砖头，砖头不够时选取消耗最大的出堆改用梯子。(大根堆)
解法一的理论复杂度应该是最低的。
class Solution {
// 优先使用梯子，梯子不够时选取差值最小的出堆改用砖头。(小根堆)
public int furthestBuilding(int[] heights, int bricks, int ladders) {
int n = heights.length, sum = 0;
QueueInteger> queue = new PriorityQueue>();
for(int i = 1; i heights.length; i++) {
int diff = heights[i] - heights[i - 1];
if(diff > 0) {
queue.offer(diff);
if(queue.size() > ladders) {
sum += queue.poll();
}
if(sum > bricks)
return i - 1;
}
}
return n - 1;
}
// 优先使用砖头，砖头不够时选取消耗最大的出堆改用梯子。(大根堆)
public int furthestBuilding2(int[] heights, int bricks, int ladders) {
int n=heights.length;
PriorityQueueInteger>pq=new PriorityQueue>((o1,o2)->((int)o2-(int)o1));
int suml=0,sumb=0;
for(int i=1;in;i++){
int diff=heights[i]-heights[i-1];
if(diff>0){
pq.add(diff);
sumb+=diff;
if(sumb>bricks){
sumb-=pq.poll();
suml++;
}
if(suml>ladders){
return i-1;
}
}
}
return n-1;
}
}
作者：onion12138
链接：https://leetcode.cn/problems/furthest-building-you-can-reach/description/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
2.3 LC871. 最低加油次数
2.3.1 解析
贪心 + 优先队列（堆）
我们可以模拟行进过程，使用 n 代表加油站总个数，idx 代表经过的加油站下标，使用 remain 代表当前有多少油（起始有 remain = startFuel)，loc 代表走了多远，ans 代表答案（至少需要的加油次数）。
只要 loc target，代表还没到达（经过）目标位置，我们可以继续模拟行进过程。
每次将 remain 累加到 loc 中，含义为使用完剩余的油量，可以去到的最远距离，同时将所在位置 stations[idx][0] loc 的加油站数量加入优先队列（大根堆，根据油量排倒序）中。
再次检查是否满足 loc target（下次循环），此时由于清空了剩余油量 remain，我们尝试从优先队列（大根堆）中取出过往油量最大的加油站并进行加油（同时对加油次数 ans 进行加一操作）。
使用新的剩余油量 remain 重复上述过程，直到满足 loc >= target 或无油可加。
容易证明该做法的正确性：同样是消耗一次加油次数，始终选择油量最大的加油站进行加油，可以确保不存在更优的结果。
作者：宫水三叶
链接：https://leetcode.cn/problems/minimum-number-of-refueling-stops/solutions/1639184/by-ac_oier-q2mk/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
class Solution {
public int minRefuelStops(int target, int startFuel, int[][] stations) {
// 使用优先队列，承装所经过加油站的油
PriorityQueueInteger> q = new PriorityQueue>((o1, o2) -> (o2 - o1));
int ans = 0, len = stations.length;
// 特判：
if (len 1) return startFuel target ? -1 : 0;
int fuel = startFuel;// 加进油箱的油(含使用过的)
// 经过可以到达的所有的加油站，背上里面的油
for (int i = 0; i len; i ++) {
while (fuel stations[i][0]) {
Integer add = q.poll();
if (add == null) return -1;
fuel += add;
ans ++;
}
q.offer(stations[i][1]);
}
// 已经经过所有的加油站仍未到达，则用车油箱和后备箱里的所剩的fuel,以期到达
while (fuel target) {
Integer add = q.poll();
if (add == null) return -1;
fuel += add;
ans ++;
}
return ans;
}
/**
题目思路：
- 将路上的一个个加油站 视为 一桶桶的油，每次经过的时候，就把油带上放后备箱；
- 当油不够的时候，取出后备箱所带的 最多的那桶油 加进油箱
- 这样以来，如若油箱和后备箱的油加起来都不够，那么就到不了了
*/
// 方法二：需要后处理
public int minRefuelStops2(int target, int startFuel, int[][] stations) {
PriorityQueueInteger> q = new PriorityQueue>((a,b)->b-a);
int re=startFuel;
int ans=0;
int n=stations.length;
int pos=0;
int idx=0;
while(postarget){
if(re==0){
if(!q.isEmpty()&&++ans>0){
re=q.poll();
}else{
return -1;
}
}
pos+=re;
re=0;
while(idxn&&pos>=stations[idx][0]){
q.add(stations[idx++][1]);
}
}
return ans;
}
}
2.4 LC630. 课程表 III (同2.2的解题思想非常相似)
class Solution {
public int scheduleCourse(int[][] courses) {
Arrays.sort(courses, (a,b)->a[1]-b[1]);
PriorityQueueInteger> q = new PriorityQueue>((a,b)->b-a);
int sum = 0;
for (int[] c : courses) {
int d = c[0], e = c[1];
sum += d;
q.add(d);
if (sum > e) sum -= q.poll();
}
return q.size();
}
}
作者：宫水三叶
链接：https://leetcode.cn/problems/course-schedule-iii/solutions/1156693/gong-shui-san-xie-jing-dian-tan-xin-yun-ghii2/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
2.5 LC45. 跳跃游戏 II(左最优问题)
class Solution {
public int jump(int[] nums) {
int n=nums.length;
int curf=0;
int ans=0;
int ml=0;// 遍历时稍带计算左侧局部最优
for(int i=0;in;i++){
if(curf>=n-1){
return ans;
}
ml=Math.max(ml,i+nums[i])服务器托管网;
if(i==curf){
ans++;
curf=ml;
}
}
return ans;
}
}
2.6 股票问题：121. 买卖股票的最佳时机（虽然使用堆的方法不是最优解，但是方便和其他题目对比得出最优解）
// 使用堆维护最小值
public int maxProfit(int[] prices) {
int n=prices.length;
//表示到第i天时，股票的历史最低点价格
PriorityQueueInteger>pq=new PriorityQueue>((o1,o2)->(o1-o2));
int max=0;
for(int i=0;in;i++){
pq.add(prices[i]);
max=Math.max(max,prices[i]-pq.peek());
}
return max;
}
3 “右最优” 类题目
3.1 LC670. 最大交换
搞懂两个问题，便可彻底理解本题的**（右最优）贪心核心**。
选择哪个数作为候选数与前面的数交换？——将最靠后的数定为候选数，若它之前出现了更大的数，则更新候选数为该数。
选择哪个数与候选数交换？——只有当候选数之前存在更小的数时，才需要交换这两数。若更靠前的位置出现小于候选数的数，则将它与候选数交换。
class Solution {
public int maximumSwap(int num) {
char[] cs = String.valueOf(num).toCharArray();
int n = cs.length, max = n - 1;
int[] maxIdx = new int[n]; // 记录每个数从当前位置往右的最大值索引
for (int i = n - 1; i >= 0; i--) {
if (cs[i] > cs[max]) max = i;
max服务器托管网Idx[i] = max;
}
for (int i = 0; i n; i++) { // 从前往后找到第一个最大值不是自己本身的数
if (cs[i] != cs[maxIdx[i]]) {
char tmp = cs[i];
cs[i] = cs[maxIdx[i]];
cs[maxIdx[i]] = tmp;
return Integer.parseInt(new String(cs));
}
}
return num;
}
}
4 同时涉及到左最优和右最优的题目
4.1 LC42 接雨水（需要两边同时进行预处理）
class Solution {
public int trap(int[] height) {
int n = height.length;
if (n == 0) {
return 0;
}
int[] leftMax = new int[n];
leftMax[0] = height[0];
for (int i = 1; i n; ++i) {
leftMax[i] = Math.max(leftMax[i - 1], height[i]);
}
int[] rightMax = new int[n];
rightMax[n - 1] = height[n - 1];
for (int i = n - 2; i >= 0; --i) {
rightMax[i] = Math.max(rightMax[i + 1], height[i]);
}
int ans = 0;
for (int i = 0; i n; ++i) {
ans += Math.min(leftMax[i], rightMax[i]) - height[i];
}
return ans;
}
}
作者：力扣官方题解
链接：https://leetcode.cn/problems/trapping-rain-water/solutions/692342/jie-yu-shui-by-leetcode-solution-tuvc/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
