8.反悔贪心

反悔贪心

https://www.cnblogs.com/Doge297778/p/16503103.html

反悔贪心基于贪心，即一开始也是按照某一贪心策略执行贪心。但是反悔贪心引入了一个新操作，即反悔。
我们可以在贪心的过程中做出一些处理，将我们假想/构造的代表反悔选项的决策同时插入决策集合，然后继续按照步骤贪心。
若之后选择了已经构造的反悔选项，代表撤销（反悔）之前的劣的决策而选用新的更优决策。

所以，反悔贪心的基本思想是：既然这次不一定是最优，那么就先放着，如果以后找到更优的再取消这次操作，选取更优的操作。
这样的话只要保证当前最优就可以了，因为以后的更优就会反悔。

维护当前最优和以后的反悔通常用堆实现。

反悔操作一个经典的应用就是网络流中寻找增广路时“建反边”的操作。

相似题目：

• 871. 最低加油次数
• LCP 30. 魔塔游戏
• 2813. 子序列最大优雅度

630. 课程表 III

困难

courses[i] = [durationi, lastDayi] 表示第 i 门课将会 持续 上 durationi 天课，并且必须在不晚于 lastDayi 的时候完成。

你的学期从第 1 天开始。且不能同时修读两门及两门以上的课程。

返回你最多可以修读的课程数目。

示例 1：

输入：courses = [[100, 200], [200, 1300], [1000, 1250], [2000, 3200]]
输出：3
解释：
这里一共有 4 门课程，但是你最多可以修 3 门：
首先，修第 1 门课，耗费 100 天，在第 100 天完成，在第 101 天开始下门课。
第二，修第 3 门课，耗费 1000 天，在第 1100 天完成，在第 1101 天开始下门课程。
第三，修第 2 门课，耗时 200 天，在第 1300 天完成。
第 4 门课现在不能修，因为将会在第 3300 天完成它，这已经超出了关闭日期。
1
2
3
4
5
6
7
8

示例 2：

输入：courses = [[1,2]]
输出：1
1
2

示例 3：

输入：courses = [[3,2],[4,3]]
输出：0
1
2

提示:

• 1 <= courses.length <= 104
• 1 <= durationi, lastDayi <= 104

https://leetcode.cn/problems/course-schedule-iii/solutions/2436667/tan-xin-huan-neng-fan-hui-pythonjavacgoj-lcwp/?envType=daily-question&envId=2023-09-11

如果能增大课程数量，就增大课程数量，如果不能增大课程数量，就在保持课程数量不变的前提下，尝试减少总时长，使得后续增大课程数量的概率增加。

经验告诉我们，在准备期未考试的时候，先考的课程先准备。同理lastDay 越早的课程，应当越早上完。但是，有的课程 duration 比较长，上完需要花很多时间，可能把这些时间花在其它课程，早就上完好几门课了。

看上去，找不到一个合适的贪心策略。别放弃!顺着这个思路，如果我们可以**[反悔]**呢?

按照 lastDay 从小到大排序，然后遍历 courses。比如先上完duration = 7 的课和 duration = 10 的课，后面遍历到了 duration = 4的课，但受到 lastDay 的限制，无法上 duration = 4 的课。此时，我们可以[撤销]前面 duration 最长的课，也就是 duration = 10 的课，这样就可以上 duration = 4 的课了! 虽然能上完的课程数目没有变化，但是由于我们多出了 10 - 4 = 6 天时间，在后续的遍历中，更有机会上完更多的课程。

在上面的讨论中，我们需要维护一个数据结构，来帮助我们快速找到duration 最长的课程。这可以用最大堆解决。

class Solution {
    public int scheduleCourse(int[][] courses) {
        // 按照 lastDay 从小到大排序
        Arrays.sort(courses, (a, b) -> a[1] - b[1]);
        // 维护最大堆，按照已经学习的课程持续时间排序
        PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b - a);
        int day = 0; // 已消耗时间
        for(int[] c : courses){
            int duration = c[0], lastDay = c[1];
            if(day + duration <= lastDay){ // 没有超过 lastDay，直接学习
                day += duration;
                pq.offer(duration);
            }else if(!pq.isEmpty() && duration < pq.peek()){  // 该课程的时间比之前的最长时间要短
                // 反悔，撤销之前 duration 最长的课程，改为学习该课程
                // 节省出来的时间，能在后面上完更多的课程
                day -= pq.poll() - duration;
                pq.offer(duration);
            }
        }
        return pq.size();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

2813. 子序列最大优雅度

困难

给你一个长度为 n 的二维整数数组 items 和一个整数 k 。

items[i] = [profiti, categoryi]，其中 profiti 和 categoryi 分别表示第 i 个项目的利润和类别。

现定义 items 的 子序列 的 优雅度 可以用 total_profit + distinct_categories*2 计算，其中 total_profit 是子序列中所有项目的利润总和，distinct_categories 是所选子序列所含的所有类别中不同类别的数量。

你的任务是从 items 所有长度为 k 的子序列中，找出 最大优雅度 。

用整数形式表示并返回 items 中所有长度恰好为 k 的子序列的最大优雅度。

**注意：**数组的子序列是经由原数组删除一些元素（可能不删除）而产生的新数组，且删除不改变其余元素相对顺序。

示例 1：

输入：items = [[3,2],[5,1],[10,1]], k = 2
输出：17
解释：
在这个例子中，我们需要选出长度为 2 的子序列。
其中一种方案是 items[0] = [3,2] 和 items[2] = [10,1] 。
子序列的总利润为 3 + 10 = 13 ，子序列包含 2 种不同类别 [2,1] 。
因此，优雅度为 13 + 22 = 17 ，可以证明 17 是可以获得的最大优雅度。 
1
2
3
4
5
6
7

示例 2：

输入：items = [[3,1],[3,1],[2,2],[5,3]], k = 3
输出：19
解释：
在这个例子中，我们需要选出长度为 3 的子序列。 
其中一种方案是 items[0] = [3,1] ，items[2] = [2,2] 和 items[3] = [5,3] 。
子序列的总利润为 3 + 2 + 5 = 10 ，子序列包含 3 种不同类别 [1, 2, 3] 。 
因此，优雅度为 10 + 32 = 19 ，可以证明 19 是可以获得的最大优雅度。
1
2
3
4
5
6
7

示例 3：

输入：items = [[1,1],[2,1],[3,1]], k = 3
输出：7
解释：
在这个例子中，我们需要选出长度为 3 的子序列。
我们需要选中所有项目。
子序列的总利润为 1 + 2 + 3 = 6，子序列包含 1 种不同类别 [1] 。
因此，最大优雅度为 6 + 12 = 7 。
1
2
3
4
5
6
7

提示：

• 1 <= items.length == n <= 105
• items[i].length == 2
• items[i][0] == profiti
• items[i][1] == categoryi
• 1 <= profiti <= 109
• 1 <= categoryi <= n
• 1 <= k <= n

class Solution {
    /*
    找到一个 base, 先选最大的 k 个利润，这可能是一个答案
    
    考虑下一个项目要不要选
    由于利润从大到小排序，利润和 total profit 不会变大
    所以重点就在 distinct_categories 能不能变大? (考虑变化量)

    分类讨论:
    1. 如果新添加的项目的类别之前选过了，那么 distinct_categories 不会变大
    2. 如果新添加的项目的类别之前没选过（没出现过）
    2.1 如果移除的项目的类别只有一个，那么 distinct_categories-1+1，不变，不行
    2.2 如果移除的项目的类别有多个，那么 distinct_categories+1，这种情况就是可以的
        - 选一个利润最小的移除，用一个栈维护
    */
    public long findMaximumElegance(int[][] items, int k) {
        Arrays.sort(items, (a, b) -> b[0] - a[0]); // 按利润从大到小排序
        long ans = 0, totalProfit = 0;
        Set<Integer> vis = new HashSet<>();
        // 因为从大到小枚举的利润，所以栈顶元素一定是最小的利润值
        Deque<Integer> duplicate = new ArrayDeque<>(); // 重复类别的利润
        for(int i = 0; i < items.length; i++){
            int profit = items[i][0], category = items[i][1];
            if(i < k){
                totalProfit += profit;
                if(!vis.add(category)) // 重复类别
                    duplicate.push(profit);
            }else if(!duplicate.isEmpty() && vis.add(category)){
                totalProfit += profit - duplicate.pop(); // 选一个重复类别中的最小利润替换
            }// else：比前面的利润小，而且类别还重复了，
            //      选它只会让 totalProfit 变小，vis.size() 不变，优雅度不会变大
            ans = Math.max(ans, totalProfit + (long)vis.size() * vis.size());
        }
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

871. 最低加油次数

困难

汽车从起点出发驶向目的地，该目的地位于出发位置东面 target 英里处。

沿途有加油站，用数组 stations 表示。其中 stations[i] = [positioni, fueli] 表示第 i 个加油站位于出发位置东面 positioni 英里处，并且有 fueli 升汽油。

假设汽车油箱的容量是无限的，其中最初有 startFuel 升燃料。它每行驶 1 英里就会用掉 1 升汽油。当汽车到达加油站时，它可能停下来加油，将所有汽油从加油站转移到汽车中。

为了到达目的地，汽车所必要的最低加油次数是多少？如果无法到达目的地，则返回 -1 。

注意：如果汽车到达加油站时剩余燃料为 0，它仍然可以在那里加油。如果汽车到达目的地时剩余燃料为 0，仍然认为它已经到达目的地。

示例 1：

输入：target = 1, startFuel = 1, stations = []
输出：0
解释：可以在不加油的情况下到达目的地。
1
2
3

示例 2：

输入：target = 100, startFuel = 1, stations = [[10,100]]
输出：-1
解释：无法抵达目的地，甚至无法到达第一个加油站。
1
2
3

示例 3：

输入：target = 100, startFuel = 10, stations = [[10,60],[20,30],[30,30],[60,40]]
输出：2
解释：
出发时有 10 升燃料。
开车来到距起点 10 英里处的加油站，消耗 10 升燃料。将汽油从 0 升加到 60 升。
然后，从 10 英里处的加油站开到 60 英里处的加油站（消耗 50 升燃料），
并将汽油从 10 升加到 50 升。然后开车抵达目的地。
沿途在两个加油站停靠，所以返回 2 。
1
2
3
4
5
6
7
8

提示：

• 1 <= target, startFuel <= 109
• 0 <= stations.length <= 500
• 1 <= positioni < positioni+1 < target
• 1 <= fueli < 109

class Solution {
    /**
    题目思路：
    - 将路上的一个个加油站 视为 一桶桶的油，每次经过的时候，就把油带上放后备箱；
    - 当油不够的时候，取出后备箱所带的 最多的那桶油 加进油箱
    - 这样以来，如若油箱和后备箱的油加起来都不够，那么就到不了了
    */
    public int minRefuelStops(int target, int startFuel, int[][] stations) {
        // 使用优先队列，承装所经过加油站的油
        PriorityQueue<Integer> 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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

LCP 30. 魔塔游戏

中等

小扣当前位于魔塔游戏第一层，共有 N 个房间，编号为 0 ~ N-1。每个房间的补血道具/怪物对于血量影响记于数组 nums，其中正数表示道具补血数值，即血量增加对应数值；负数表示怪物造成伤害值，即血量减少对应数值；0 表示房间对血量无影响。

小扣初始血量为 1，且无上限。假定小扣原计划按房间编号升序访问所有房间补血/打怪，为保证血量始终为正值，小扣需对房间访问顺序进行调整，每次仅能将一个怪物房间（负数的房间）调整至访问顺序末尾。请返回小扣最少需要调整几次，才能顺利访问所有房间。若调整顺序也无法访问完全部房间，请返回 -1。

示例 1：

输入：nums = [100,100,100,-250,-60,-140,-50,-50,100,150]

输出：1

解释：初始血量为 1。至少需要将 nums[3] 调整至访问顺序末尾以满足要求。

示例 2：

输入：nums = [-200,-300,400,0]

输出：-1

解释：调整访问顺序也无法完成全部房间的访问。

提示：

• 1 <= nums.length <= 10^5
• -10^5 <= nums[i] <= 10^5

https://leetcode.cn/problems/p0NxJO/solutions/702009/javatan-xin-you-xian-dui-lie-shuang-bai-3r7fb/

class Solution {
    /**
    首先，我们计算一遍所有回合之后的血量，如果是负数，则直接返回-1 
    然后我们模拟过程，将之前扣减的血量都放入优先队列中，
    每次快死之前，就取出堆顶的元素（扣最多的血）给自己加上，
    这样的贪心思想能保证我们移动到尾部的元素是最少的。
     */
    public int magicTower(int[] nums) {
        int sum = 1;
        for(int num : nums) sum += num;
        if(sum <= 0) return -1;

        long blood = 1;
        // 维护堆顶血量最小（注意是元素都是负数）
        PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> a-b);
        int last = 0;
        for(int num : nums){
            if(num < 0){
                pq.offer(num);
                // 这回合过后就要死了，需要把前面扣最多的血移到最后去
                if(blood + num <= 0){
                    last++; // 移动次数加一
                    blood -= pq.poll();// 加回之前扣除最多的血量
                }
            }
            blood += num;
        }
        return last;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

其他（反悔贪心 + 单调栈）

2866. 美丽塔 II

中等

给你一个长度为 n 下标从 0 开始的整数数组 maxHeights 。

你的任务是在坐标轴上建 n 座塔。第 i 座塔的下标为 i ，高度为 heights[i] 。

如果以下条件满足，我们称这些塔是 美丽 的：

1. 1 <= heights[i] <= maxHeights[i]
2. heights 是一个 山脉 数组。

如果存在下标 i 满足以下条件，那么我们称数组 heights 是一个 山脉 数组：

• 对于所有 0 < j <= i ，都有 heights[j - 1] <= heights[j]
• 对于所有 i <= k < n - 1 ，都有 heights[k + 1] <= heights[k]

请你返回满足 美丽塔 要求的方案中，高度和的最大值 。

示例 1：

输入：maxHeights = [5,3,4,1,1]
输出：13
解释：和最大的美丽塔方案为 heights = [5,3,3,1,1] ，这是一个美丽塔方案，因为：
- 1 <= heights[i] <= maxHeights[i]  
- heights 是个山脉数组，峰值在 i = 0 处。
13 是所有美丽塔方案中的最大高度和。
1
2
3
4
5
6

示例 2：

输入：maxHeights = [6,5,3,9,2,7]
输出：22
解释： 和最大的美丽塔方案为 heights = [3,3,3,9,2,2] ，这是一个美丽塔方案，因为：
- 1 <= heights[i] <= maxHeights[i]
- heights 是个山脉数组，峰值在 i = 3 处。
22 是所有美丽塔方案中的最大高度和。
1
2
3
4
5
6

示例 3：

输入：maxHeights = [3,2,5,5,2,3]
输出：18
解释：和最大的美丽塔方案为 heights = [2,2,5,5,2,2] ，这是一个美丽塔方案，因为：
- 1 <= heights[i] <= maxHeights[i]
- heights 是个山脉数组，最大值在 i = 2 处。
注意，在这个方案中，i = 3 也是一个峰值。
18 是所有美丽塔方案中的最大高度和。
1
2
3
4
5
6
7

提示：

• 1 <= n == maxHeights <= 105
• 1 <= maxHeights[i] <= 109

贪心思想，假设枚举到i时，i就是当前[i,n)最小的值。先加入单调栈，当枚举到j，j并且nums[j] < nums[i]，则撤销i的贡献，即a[i] * (n-i)，将[j, n-1]的贡献加入sum中，即a[j] * (n-j)

class Solution {
    /** 
    10^5 次方数据，枚举每个点作为最大值会超时，怎么优化呢？
    计算从 a[0] 到 a[i] 形成山状数组的左侧递增段，元素和最大是多少，记到数组 pre[i] 中。
    计算从 a|i] 到 a[n-1] 形成山状数组的右侧递减段，元素和最大是多少，记到数组 suf[i] 中。
    答案就是 pre[i] + suf[i+1] 的最大值

    如何计算 pre 和 suf？ 单调栈
    用单调栈，元素值从栈底到栈顶严格递增
    以 suf 为例，我们从右往左遍历 a，设当前得到的元素和为 sum
    1. 如果 a[i] 大于栈顶的元素值，那么直接把 a[i] 加到 sum 中，同时把i入栈 (栈中只需要保存下标)
    2. 否则，只要 a[i] 小于等于栈顶元素值，就不断循环，把之前加到sum 的撤销掉。
            循环结束后，从 a[i] 到 a[j-1] (假设现在栈顶下标是 j) 都必须是 a，
            把 a[i]*(j-1) 加到 sum 中
     */
    public long maximumSumOfHeights(List<Integer> maxHeights) {
        int[] a = maxHeights.stream().mapToInt(i -> i).toArray();
        int n = a.length;
        long[] suf = new long[n+1];
        Deque<Integer> st = new ArrayDeque<>();
        st.push(n); // 哨兵
        long sum = 0;
        // 计算suf
        for(int i = n-1; i >= 0; i--){
            int x = a[i];
            while(st.size() > 1 && x <= a[st.peek()]){
                int j = st.pop(); // 撤销之前加到 sum 中的
                sum -= (long)a[j] * (st.peek() - j);
            }
            sum += (long) x * (st.peek() - i); // 从 i 到 st.peek()-1 都是 x
            suf[i] = sum;
            st.push(i);
        }
        long ans = sum;
        st.clear();
        st.push(-1); // 哨兵
        long pre = 0;
        for(int i = 0; i < n; i++){
            int x = a[i];
            while(st.size() > 1 && x <= a[st.peek()]){
                int j = st.pop();// 撤销之前加到 sum 中的
                pre -= (long) a[j] * (j - st.peek());
            }
            pre += (long) x * (i - st.peek());// 从 st.peek()+1 到 i 都是 x
            ans = Math.max(pre + suf[i+1], ans);
            st.push(i);
        }
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50