[数据结构与算法][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;
}

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;
}

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;
}

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;
}

300. 最长递增子序列

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

所以对于一系列相同长度的最长递增子序列，我们都贪心地选择末尾元素最小的一个，并使用一个数组 min 保存每个长度的最长递增子序列的末尾元素，即，min[i] 表示长度为 i 的最长递增子序列的末尾元素

public int lengthOfLIS(int[] nums) {
    int n = nums.length;
    if (n == 0) {
        return 0;
    }
    int[] min = new int[n + 1];
    int len = 1; //len表示当前找到的最长递增子序列的长度
    min[len] = nums[0]; //初始置长度为1的最长递增子序列的末尾元素为nums[0]
    for (int i = 1; i < n; ++i) {
        //如果遍历到的新数大于当前最长递增子序列的最后一个元素，就更新最长递增子序列的长度
        if (nums[i] > min[len]) { 
            min[++len] = nums[i];
        } else {
        	//否则就找到min数组中第一个大于nums[i]的元素位置，将其min值变小为nums[i]，此步即为算法中的“贪心”操作
            int l = 1, r = len;
            while (l <= r) {
                int mid = (l + r) >> 1;
                if (min[mid] < nums[i]) {
                    pos = mid;
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }
            }
            //经过上述的二分查找过程mid所在的就是min数组中最后一个小于nums[i]的元素的位置，
            //l所在的就是第一个大于/等于nums[i]的元素位置。那么由于min[l]大于nums[i]，说明长度为l的
            //最长递增子序列的最小末尾元素就应更改为nums[i]
            //当然也有可能min数组中所有元素值都大于/等于nums[i]，也就是说nums[i]是当前所有已遍历的数中最小的，
            //此时就应该更新min[1]为nums[i]
            min[l] = nums[i];
        }
    }
    return len;
}

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;
    }
}

435. 无重叠区间

题目说 “返回需要移除区间的最小数量，使剩余区间互不重叠”，换一个角度来说意思就是从所有区间中选无重叠区间最多能选出多少个

如果我们从左往右选区间，为了后续能选出更多的区间，我们应该贪心地选择 右边界更小 的区间，这样右边剩余的空间更多，可以选出的区间也就会更多

因此，我们先将所有区间按照右边界大小进行升序排序，然后从左往右开始选区间，每选一个区间，记录其右边界 lastRight，再继续往右遍历时遇到的第一个左边界大于等于 lastRight 的区间就是要选的下一个区间，因为所有区间已经按照右边界从小到大排序，选出的区间只需要再满足一个 “无重叠” 的条件即可

public int eraseOverlapIntervals(int[][] intervals) {
    int len = intervals.length;
    //1. 根据区间右边界排序
    Arrays.sort(intervals,(a,b)-> a[1] - b[1]);
    int ans = 1; //记录答案，即没有重叠的区间个数
    int lastRight = intervals[0][1]; //上一个无重叠区间的右边界
    for(int i = 1;i < len;i++){
        //2. 遍历寻找每一个无重叠区间。右边界已经按照从小到大排序
        //所以lastRight右边第一个左边界不与lastRight重叠的区间即为下一个无重叠区间
        if(intervals[i][0] >= lastRight){
            ans++;
            lastRight = intervals[i][1];
        }
    }
    return len - ans; //总区间数减掉选出来的无重叠区间数就是要移除的重叠区间数
}