Leetcode 刷题笔记——贪心

Posted on In Symbols count in article: 4.2k Reading time ≈ 4 mins.
  • 贪心的核心思想是每一步都选择当前的局部最优解，从而最终获得全局最优解。
  • 通常来说，一个问题的贪心解法比动态规划解法高效，而且更加直观，易于实现，所以我们可以首先考虑是否能用贪心来做，然而难点在于如何证明贪心的正确性。
  • 贪心的题目变化多端，我们学习的更多是一种思维方式。但也有一些经典的题目类型（如区间重合问题），其原理大同小异。

435. 无重叠区间

给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。

将区间按右边界升序排序，这样我们每次都优先考虑右边界较小的区间，从而给之后的区间留出更多的空间，贪心的思想便体现在此。

此外，我们维护一个表示所有已保留区间的最右边界的变量 end 。如果当前区间的左边界小于 end ，则说明与之前已保留的区间重叠了，我们必须舍弃它；如果当前区间的左边界大于等于 end ，则不会发生重叠，我们将 end 更新为这个区间的右边界。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        if (intervals == null || intervals.length == 0) {
            return 0;
        }

        Arrays.sort(intervals, (x, y) -> x[1] - y[1]);
        int res = 0;
        int end = intervals[0][1];
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] >= end) {
                end = intervals[i][1];
            } else {
                res++;
            }
        }
        return res;
    }
}

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

在二维空间中有许多球形的气球。对于每个气球，提供的输入是水平方向上，气球直径的开始和结束坐标。由于它是水平的，所以y坐标并不重要，因此只要知道开始和结束的x坐标就足够了。开始坐标总是小于结束坐标。平面内最多存在104个气球。

一支弓箭可以沿着x轴从不同点完全垂直地射出。在坐标x处射出一支箭，若有一个气球的直径的开始和结束坐标为 xstart，xend， 且满足 xstart ≤ x ≤ xend，则该气球会被引爆。可以射出的弓箭的数量没有限制。 弓箭一旦被射出之后，可以无限地前进。我们想找到使得所有气球全部被引爆，所需的弓箭的最小数量。

我一开始的想法是先找到当前重合气球最多的点，用一支箭引爆，以此类推，直到所有气球都被引爆。但其实这样做不仅难以用合适的数据结构实现，而且完全没有必要。贪心的重点就在于每次只做当前局部最优的操作，而我这种思路实际上每次都在寻找全局最优解，可以说是把简单问题复杂化了。

其实我们仔细一想就能发现，这道题与上一题本质上是一致的，而逻辑恰好相反：上题是在发生重合时记一次数，而本题是在不重合时记一次数（需要一支新的箭来引爆气球）。

因此，仍然是先按右界排序，这样做是为了保证当气球的左界小于等于 end 时，当前积累的所有气球一定都发生重合，即一定可以用一支箭全部引爆。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int findMinArrowShots(int[][] points) {
        if (points == null || points.length == 0) {
            return 0;
        }

        Arrays.sort(points, (x, y) -> x[1] - y[1]);
        int res = 1;
        int end = points[0][1];
        for (int i = 1; i < points.length; i++) {
            if (points[i][0] > end) {
                res++;
                end = points[i][1];
            }
        }
        return res;
    }
}

763. 划分字母区间

字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一个字母只会出现在其中的一个片段。返回一个表示每个字符串片段的长度的列表。

这道题我一开始做的时候想到了要记录每个字母的起始位置和最后一次出现的位置，但企图通过这些区间的交并关系直接给出题目要求的划分点，最后在实现的时候成功把自己绕晕了。问题就在于，这样做仍然是以宏观的、整体的角度去看待输入字符串，这完全不是“贪心”的思维方式，且往往非常难以实现，正如我在452题陷入的困境一样。

实际上，这道题的确需要事先记录好每个字母最后一次出现的位置，但在寻找划分点的时候，应该是以从左到右一边扫描一边更新的方式去逐步解决，即贪心思想所一直强调的：通过当前子问题的局部最优最终达到全局最优。

在上述思想的指导下，正确的思路应该是：设定当前的起始字母位置 start ，从左到右扫描至其最后一次出现的位置 end ，期间如果遇到其他字母的最后一次出现位置在 end 之后，则更新 end 为该位置，直到扫描到达 end ，表示此处应有一个划分，然后重新设置 start 为 end + 1 ，重复上述过程。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public List<Integer> partitionLabels(String S) {
        int[] last = new int[26];
        for (int i = 0; i < S.length(); i++) {
            last[S.charAt(i) - 'a'] = i;
        }

        List<Integer> res = new ArrayList();
        int start = 0;
        int end = last[S.charAt(0) - 'a'];
        for (int i = 0; i < S.length(); i++) {
            end = Math.max(end, last[S.charAt(i) - 'a']);
            if (i == end) {
                res.add(end - start + 1);
                start = i + 1;
            }
        }
        return res;        
    }
}

55. 跳跃游戏

给定一个非负整数数组，你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个位置。

扫描数组的过程中，不断更新所能到达的最远位置 maxi ，如果当前位置已经超出了 maxi ，则说明无法到达最后一个位置。

1
2
3
4
5
6
7
8
9
10
class Solution {
    public boolean canJump(int[] nums) {
        int maxi = 0;
        for (int i = 0; i < nums.length; i++) {
            if (maxi < i) return false;
            maxi = Math.max(maxi, i + nums[i]);
        }
        return true;   
    }
}

45. 跳跃游戏 II

给定一个非负整数数组，你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

你的目标是使用最少的跳跃次数到达数组的最后一个位置。

这题我最开始写的解法思路是对下一个位置所能到达的最远位置贪心，即并不是每次跳到当前所能跳到的最远位置，而在这个最远位置范围内选择下一个位置，从这个位置开始跳所能到达的位置最远。

这个贪心策略本身没问题，只是我实现的时候只能写成 \(O(n^2)\) 的复杂度，而且代码特别丑，总觉得应该有更高效的实现方法。之后果然在题解中找到了和我思路一致但只需要一遍扫描的写法，如下所示，非常巧妙。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int jump(int[] nums) {
        int res = 0;
        int maxi = 0, end = 0;
        for (int i = 0; i < nums.length - 1; i++) {
            maxi = Math.max(maxi, i + nums[i]);
            if (i == end) {
                res++;
                end = maxi;
            }
        }
        return res;
    }
}

376. 摆动序列

如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为摆动序列。第一个差（如果存在的话）可能是正数或负数。少于两个元素的序列也是摆动序列。

例如， [1,7,4,9,2,5] 是一个摆动序列，因为差值 (6,-3,5,-7,3) 是正负交替出现的。相反, [1,4,7,2,5] 和 [1,7,4,5,5] 不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。

给定一个整数序列，返回作为摆动序列的最长子序列的长度。 通过从原始序列中删除一些（也可以不删除）元素来获得子序列，剩下的元素保持其原始顺序。

从左向右扫描数组，通过计算两两连续元素的差值得出当前的趋势是上升还是下降。如果前一次上升的，且当前仍然是上升的，则应该舍弃前一个元素而取当前元素为最大值，即将当前最大值尽可能提高，因为摆动序列需要的下一个元素是下降的。反之亦然。

事实上，上述策略等价于只取数组中的所有波峰波谷元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int wiggleMaxLength(int[] nums) {
        int n = nums.length;
        if (n <= 1) return n;

        int res = 1;
        int curr, prev = 0;
        for (int i = 1; i < n; i++) {
            curr = nums[i] - nums[i-1] ;
            if ((curr > 0 && prev <= 0) || (curr < 0 && prev >= 0)) {
                prev = curr;
                res++;
            }
        }
        return res;
    }
}