思想

所谓贪心算法，起的非常合适：做决策的时候，永远选择 most 的。我觉得很多算法其实都是在做决策，比如回溯法，到底什么时候要终止递归，什么时候到下一层？因此贪心算法更像是一种思想，与其他算法存在交叉。

举个很浅显的例子，走迷宫，面前有几个分岔路，路标上分别写着距离目的地的距离。贪心算法每次都选择当前格局下最好的选择，也就是路标上最短的路。

然而，当前状态最短不一定到了下一个状态还更短。换言之，局部最优不一定等于全局最优。就有些类似于人生道路上的抉择。而贪心如果按照 CS50 AI 的分类，算是搜索专题下的一种，除了贪心之外，还包含 BFS、DFS、A* 等等，就不再赘述了。

思想明白了，如果真的要写一个贪心算法，不一定能转的过来，写的非常准确。所以还是看看例题。

例题

45. Jump Game II

这题当时似乎是算法课的作业。给了一个数组，数组中的每个元素值表示从该位置最远可向前跳几格。保证肯定能够跳到 n - 1，问最少跳几次。

这题有点层次遍历的味道。设置两个 bar，一个(end)表示当前轮次的末尾，另一个(farthest)表示下一轮次的末尾。当碰到 end 时， step++。

讨论两件事：

  1. 为什么循环终止判断是 i < n - 1，因为题目保证 n - 1 一定可以到达，没必要站在 [n-1] 进行判断，下一题就不可这样写了；
  2. 可以在循环中用一个提前的条件判断来提早终止，小优化，不一定有推广。

这怎么贪心了呢？我认为，是每一跳都想走的最远。farthest = max(farthest, nums[i] + i)。嗯，如果有一跳没有选择这一跳能到达最远的格子(farthest)作为起点进行下一次跳跃，会有一些无用功。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int jump(vector<int>& nums) {
        int end = 0;
        int farthest = 0;
        int step = 0;
        int n = nums.size();

        for (int i = 0; i < n - 1; i++) {
            farthest = max(farthest, nums[i] + i);

            if (i == end) {
                end = farthest;
                step++;

                if (end >= n - 1) break;
            }
        }

        return step;
    }
};

55. Jump Game

这题和上一题略有不同，有可能跳不到终点。

解法比上一题稍微简单些，因为没必要维护两个 bar，只需要看看能跳到最远的地方是哪里便 OK 了。如果当前下标超过了最远能到达的地方，则返回假。

这里的循环终止条件就不能是 i < n - 1，因为不一定 [n-2] 就一定能走到最后。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    bool canJump(vector<int>& nums) {
        int farthest = 0;
        int n = nums.size();

        for (int i = 0; i < n; i++) {
            if (i > farthest) return false;
            farthest = max(farthest, nums[i] + i);
        }

        return true;
    }
};

121. Best Time to Buy and Sell Stock

这题是买股票。给了一串数字，低买高卖，找到最大的利润。

思路比较简单，真的是贪心。需要记录之前见过的最小值（「如果我当时买入就好了」）。以及对于每个当前值，计算能获得的最大利润。

不需要记录见过的最大值，因为必须先买再卖，如果历史上出现过一个高值，不可能现在买入，在几天前卖出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int profit = 0;
        int low = INT_MAX;

        for (int price : prices) {
            low = min(low, price);
            profit = max(profit, price - low);
        }

        return profit;
    }
};

763. Partition Labels

这题希望我们给字符串进行切分，切得越碎越好，但是必须保证同种字母，只能在一个片段中出现。比如 "ab"、"a" 非法，因为 "a" 出现在两个片段里。

这题的思路，算是给我一个启发。我之前在解决算法题的时候，总期望一步到位，只需要写一份核心算法。但这道题提示我，还需要进行准备工作。先用一个数组记录每种字母最后出现的位置。在后面的算法中利用这一数组，贪心地更新当前片段的结尾至少是多远。

此外，如果看题干，会认为这道题需要用到 substr 等函数，其实并不需要，记录下标便可解决问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    vector<int> partitionLabels(string s) {
        vector<int> last(26);
        vector<int> res;

        for (int i = 0; i < s.size(); i++) {
            last[s[i] - 'a'] = i;
        }

        int start = 0, end = 0;

        for (int i = 0; i < s.size(); i++) {
            end = max(end, last[s[i] - 'a']);

            if (i == end) {
                res.push_back(end - start + 1);
                start = i + 1;
            }
        }

        return res;
    }
};