[LeetCode]-贪心

前言

记录刷 LeetCode 时遇到的贪心算法相关题目，第一篇

452. 用最少数量的箭引爆气球

看到区间操作，本来想用差分来做的，写完了一测，数组太大，因为有个样例 [[-2147483646,-2147483645],[2147483646,2147483647]]。所以想看看能不能调整一下数组下标对应关系，一看题意，每个气球区间的取值是 [-2³¹,2³¹ - 1]，看来怎么调都不行了
那就看题解了

为了使用最少的箭，我们每只箭都贪心地选在某个气球 i 的 x_end 处，那么它往后的气球中只要其 x_start 小于等于 i 的 x_end，都可以被同一只箭刺穿。因此首先按照 x_end 进行升序排序，然后选取第一个 x_end 作为第一只箭的位置，然后往后遍历看有多少气球能一起被这只箭刺穿，一旦找到某个气球的 x_start 大于第一只箭的位置的，这个气球的 x_end 就作为下一只箭的位置，然后以此类推

public int findMinArrowShots(int[][] points) {
    if (points.length == 0) {
        return 0;
    }
    Arrays.sort(points, new Comparator<int[]>() {
        public int compare(int[] point1, int[] point2) {
            //要升序排序，本来习惯写类似于 return o1.val - o2.val 来实现，这里由于样例中有出现
            //[[-2147483646,-2147483645],[2147483646,2147483647]] 这样的例子，加减法会溢出，所以只能通过比较来实现
            if (point1[1] > point2[1]) {
                return 1;
            } else if (point1[1] < point2[1]) {
                return -1;
            }
            return 0;
        }
    });
    int pos = points[0][1];
    int ans = 1;
    for (int[] balloon: points) {
        if (balloon[0] > pos) {
            pos = balloon[1];
            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

55. 跳跃游戏

要想知道能不能到达最后一个位置，我们只需要维护每跳一步所能到达的最远位置 maxFar，只要发现 maxFar 大于等于最后一个位置的位置，那就可以立马判定能够到达最后一个位置。所以我们只需要贪心地计算并维护这个最远距离即可

public boolean canJump(int[] nums) {
    int len = nums.length;
    int maxFar = 0;
    for (int i = 0; i < len; i++) {
    	//与跳跃游戏Ⅱ不同，这里有可能跳不到终点：如果当前位置已经超出了前面所能跳到的最远距离，就说明无法继续往后跳了
        if (i > maxFar) return false;
        maxFar = Math.max(maxFar, i + nums[i]); //维护最远距离
        if(maxFar >= len - 1) return true; //发现最远距离已经达到最后一个位置直接返回true
    }
    return true;
}
1
2
3
4
5
6
7
8
9
10
11

45. 跳跃游戏 II

假设 nums[0] 等于 x (x 肯定大于等于1)，那么第一步所能跳出的范围就为 [1,x]，这并不是说我们就要这第一步就一定要去到 x，这是局部最优解但并不一定能得到全局最优解

我们应该想到的是，[1,x] 是我们第一跳所能跳到的范围，换句话说，第一跳的目标位置可以是这个区间中任意一个位置，再换句话说，第二跳的起始位置必须是这个区间中的位置，但 可以是这个区间中的任何一个位置

所以，对于这个区间中的每一个位置 i，我们都可以去计算它们往后跳一步所能到达的最远位置，即 i + nums[i]，其中最大的一个结果，不就是第二跳所能到达的最远距离吗，确切的说，是第一 + 第二跳所能跳到的最远位置。虽然可以，但我们没必要知道跳出这个最远距离的起始位置具体是哪，只需要知道它小于 x —— 上一跳的最远位置，即可。其实，我们也没必要知道第一跳的范围是 [1,x]，我们只需要知道最远位置是 x 即可，可以把坐标 0 看成是第 0 跳的最远位置，这样第一跳也就不具特殊性了

以这种策略计算下去，很显然最终得到的就会是全局最小跳数

虽然没提到 贪心 二字，但其实我们的算法中，每一跳的 最远 距离是一个很重要的考量，也可以看成是贪心的体现之处了

要注意题目说明了总是可以到达最后一个位置，所以不用考虑跳到中间无法继续跳下去的情况

public int jump(int[] nums) {
    int length = nums.length;
    int lastJumpMaxFar = 0; //记录上一跳所能到达的最远位置
    int maxPosition = 0; //维护更新下一跳所能到达的最远位置
    int steps = 0;       //记录最终步数
    for (int i = 0; i < length - 1; i++) {
        maxPosition = Math.max(maxPosition, i + nums[i]);
        //可以尝试提前跳出循环，可能不用遍历整个数组
        if(maxPosition >= length - 1) return steps + 1; 
        //已经跳到了上一跳所能到达的最远位置，还想往后的话，必须再跳一步，
        //且这一步所能跳到的最远距离就是 maxPosition
        if (i == lastJumpMaxFar) { 
            lastJumpMaxFar = maxPosition;
            steps++;
        }
    }
    return steps;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

1353. 最多可以参加的会议数目

对于在某个时间点时一系列可以参加的会议中，应该贪心选择其中结束时间最小的一个
即对于某个时间点 day (从 1 开始，即第一天)，可能有一系列开始时间小于等于 day，结束时间大于等于 day 的会议，那么对于这个时间点要参加哪个会议，应该贪心地选择结束时间最小的一个，因为结束时间更大的会议的选择空间更大

由于每个时间点的选择随着时间点 day 的变化会不断变化，需要动态维护

所以就需要使用到 堆/优先队列，而且是要选择结束时间最小的，所以要是一个元素为会议结束时间的小顶堆
首先对所有会议按照会议的开始时间进行升序排序，因为我们需要先根据开始时间判断哪些会议在某个时间点 day 有可能被参加，这就需要会议的开始时间小于等于 day
然后就从 1 开始枚举每一天 day，将所有开始时间小于等于 day 的会议的结束时间都添加到堆中，然后再将所有结束时间小于 day 的会议的结束时间弹出堆。剩下的就是所有开始时间小于等于 day，结束时间大于等于 day 的会议，再在其中选取一个结束时间最小的，也即此时的堆顶元素，对应的会议去参加即可

public int maxEvents(int[][] events) {
    PriorityQueue<Integer> queue = new PriorityQueue<Integer>();
    //按照会议开始时间
    Arrays.sort(events, (a,b) ->  a[0] - b[0]);
    int i = 0, res = 0, n = events.length;
    int day = 1;                            //day表示每一天
    while(i < n || !queue.isEmpty()){
        //将每个当前时间有可能进行的会议的结束时间添加到优先队列中
        while (i < n && events[i][0] <= day){
            queue.offer(events[i++][1]);
        }
        //到这里，队列中放的都是开始时间小于等于当前时间点的会议的结束时间
        //所以，排除掉结束时间小于当前时间点的会议
        while (queue.size() > 0 && queue.peek() < day){
            queue.poll();
        }
        //排除后，堆顶元素就是开始时间小于等于当前时间点，结束时间大于等于当前时间点，且结束时间最小的一个
        //所以选择这个会议去参加，这一步即为整个算法的 贪心 所在
        if (queue.size() > 0) {
            queue.poll();
            res++;
        }
        day++;
    }
    return res;
}
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

300. 最长递增子序列

对于一个递增子序列，如果末尾元素是较小的，那么在后续找到更多大于这个末尾元素的数的可能性就更大，也就是说到最后找到的最长递增子序列就会更长

所以对于一系列相同长度的最长递增子序列，我们都贪心地选择末尾元素最小的一个，并使用一个数组 min 保存各个长度的最长递增子序列的末尾元素，即 min[i] 表示长度为 i 的最长递增子序列的最小末尾元素，同时我们使用 maxLen 变量维护当前找到的最长子序列的长度

然后我们遍历每个数组元素 nums[i]，如果 nums[i] 大于 min[maxLen]，即比当前找到的最长递增子序列的末尾元素大，那么我们自然可以更新最长子序列的长度为 maxLen + 1，同时更新这个长度对应的末尾元素为 nums[i]

反之，如果 nums[i] 小于等于 min[maxLen]，说明我们无法更新最长递增子序列的长度。但此时可以进行我们的贪心操作：既然 nums[i] 小于等于当前最长递增子序列的末尾元素，那么我们可以找到某个小于等于 maxLen 的长度，满足长度为 j 的递增子序列的最小末尾元素大于 nums[i] 但是长度为 j - 1 的递增子序列的最小末尾元素小于 nums[i]，这样我们就可以把长度为 j 的递增子序列的最小末尾元素 min[j] 更新为 nums[i]

遍历完数组后的 maxLen 就是最长递增子序列的长度

public int lengthOfLIS(int[] nums) {
    if (nums.length == 0) {
        return 0;
    }
    int maxLen = 1,numsLen = nums.length;
    //最长递增子序列的长度可以是nums.length，所以数组大小要为nums.length+1
    int[] min = new int[numsLen + 1];
    //初始化长度为1的递增子序列的末尾元素为nums[0]
    min[maxLen] = nums[0];
    for (int i = 1; i < numsLen; ++i) {
        if (nums[i] > min[maxLen]) {
            min[++maxLen] = nums[i];
        }else{
            //可以发现min数组是具有递增性的，所以可以用二分查找
            //如果找不到说明所有的数都比 nums[i] 大，此时要更新 min[1]，所以这里将 pos 设为 0
            int l = 1, r = maxLen, pos = 0;
            while (l <= r) {
                int mid = (l + r) >> 1;
                if (min[mid] < nums[i]) {
                    pos = mid;
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }
            }
            //找到j(即pos+1)满足 min[j] > nums[i] && min[j - 1] < nums[i]
            min[pos + 1] = nums[i];
        }
    }
    return maxLen;
}
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

贪心+二分

1011. 在D天内送达包裹的能力

对于最值问题，优先考虑 贪心＋二分 的做法是否可行 (谁能拒绝二分呢)
这道题中对一天要送的包裹的重量进行二分，二分的左边界，也即一天要送的最小重量，就是所有包裹中质量最大的，否则这个最大的永远都送不出去；二分的右边界，就是所有包裹都放在一天去送，即所有包裹的重量
计算当一天送出的最大包裹数量为 mid 的时候所需的天数 day，如果 day 小于等于 days，说明可能可以减少一天送出的最大包裹重量，更新 r = mid；day 大于 days 的话，说明要增大一天送出的最大包裹重量，更新 l = mid + 1，为什么是 mid + 1 不是 mid，因为此时的 mid 已经不符合条件了，后续不需要再考虑它，而day <= days 的话，可能这个 mid 就是答案，所以 r = mid 而不是 mid - 1

class Solution {
    public int shipWithinDays(int[] weights, int days) {
        int l = -1,r = 0,mid; //二分左边界是
        for(int i : weights){
            l = l > i ? l : i;
            r += i;
        }
        while(l < r){
            mid = (l + r) >> 1;
            int day = 1,oneDayWeights = 0;
            for(int i : weights){
                if(oneDayWeights + i > mid){
                    day++;
                    oneDayWeights = 0;
                }
                oneDayWeights += i;
            }
            if(day <= days){
                r = mid;
            }else{
                l = mid + 1;
            }
        }
        return l;
    }
}
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

410. 分割数组的最大值

这种在 k 次机会内，求最值的问题都可以考虑是否可以用贪心＋二分的方法完成

单个分割数组的和，右边界为把整个数组作为一个分割集，那么对应的值为数组中的元素总和；左边界为把整个数组中每个元素作为一个分割集，此时对应的各个分割集的各自和的最大值为数组中最大元素的值

确定好左右边界就可以开始二分，每次二分出一个值作为分割数组各自和的最大值，然后根据这个最大值对原数组进行划分，划分的具体方法就是遍历数组，把遍历到的元素加入到当前的分割集中，如果当前分割集的总和已经超过了最大值，就将划分次数加一，然后把当前元素作为新的下一个分割集。最后判断划分次数跟 k 的关系，如果划分次数大于 k，说明基于本次最大值的划分并不符合条件，而且这个最大值太小了，才会导致划分次数过大，所以需要把这个各自和最大值放大，于是更新 left = mid + 1，注意不是 mid，因为 mid 对应的解是不符合条件的，所以没必要再包含 mid 了；如果划分次数小于等于 k，所以我们可以找到可行解，但是可能有多个可行解，我们要找到是满足条件的最小的各自和的最大值，所以我们要继续往更小的方向去找，更新 right = mid，这里就需要取 mid，因为我们可能在更小的范围中找不到更小的可行解，此时就需要保留 mid，作为 “保底” 的解

public int splitArray(int[] nums, int k) {
    int left = 0,right = 0;
    for(int i : nums){
        if(left < i){
            left = i;
        }
        right += i;
    }
    int mid = 0,curCount = 1,sum = 0;
    while(left < right){
        mid = (left + right) >> 1;
        curCount = 1;
        sum = 0;
        for(int i : nums){
            if(sum + i > mid){
                sum = i;
                curCount++;
            }else{
                sum += i;
            }
        }
        if(curCount > k){
            left = mid + 1;
        }else{
            right = mid;
        }
    }
    return left;
}
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