【算法】贪心

贪心算法（greedy algorithm，又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解 。

算法思路

贪心算法一般按如下步骤进行：

1. 建立数学模型来描述问题。
2. 把求解的问题分成若干个子问题。
3. 对每个子问题求解，得到子问题的局部最优解。
4. 把子问题的解局部最优解合成原来解问题的一个解。

贪心算法是一种对某些求最优解问题的更简单、更迅速的设计技术。贪心算法的特点是一步一步地进行，常以当前情况为基础根据某个优化测度作最优选择，而不考虑各种可能的整体情况，省去了为找最优解要穷尽所有可能而必须耗费的大量时间。贪心算法采用自顶向下，以迭代的方法做出相继的贪心选择，每做一次贪心选择，就将所求问题简化为一个规模更小的子问题，通过每一步贪心选择，可得到问题的一个最优解。虽然每一步上都要保证能获得局部最优解，但由此产生的全局解有时不一定是最优的，所以贪心算法不要回溯。

算法特性

贪心算法可解决的问题通常大部分都有如下的特性：

• 有一个以最优方式来解决的问题。为了构造问题的解决方案，有一个候选的对象的集合：比如不同面值的硬币。
• 随着算法的进行，将积累起其他两个集合：一个包含已经被考虑过并被选出的候选对象，另一个包含已经被考虑过但被丢弃的候选对象。
• 有一个函数来检查一个候选对象的集合是否提供了问题的解答。该函数不考虑此时的解决方法是否最优。
• 还有一个函数检查是否一个候选对象的集合是可行的，即是否可能往该集合上添加更多的候选对象以获得一个解。和上一个函数一样，此时不考虑解决方法的最优性。
• 选择函数可以指出哪一个剩余的候选对象最有希望构成问题的解 。
• 最后，目标函数给出解的值。

使用条件

利用贪心法求解的问题应具备如下2个特征。
1、贪心选择性质
一个问题的整体最优解可通过一系列局部的最优解的选择达到，并且每次的选择可以依赖以前作出的选择，但不依赖于后面要作出的选择。这就是贪心选择性质。对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。
2、最优子结构性质
当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用贪心法求解的关键所在。在实际应用中，至于什么问题具有什么样的贪心选择性质是不确定的，需要具体问题具体分析。

解题策略

贪心算法不从整体最优上加以考虑，所做出的仅是在某种意义上的局部最优选择。使用贪心策略要注意局部最优与全局最优的关系，选择当前的局部最优并不一定能推导出问题的全局最优。贪心策略解题需要解决以下两个问题：

1. 该问题是否适合使用贪心策略求解，也就是该问题是否具有贪心选择性质 ；
2. 制定贪心策略，以达到问题的最优解或较优解。

要确定一个问题是否适合用贪心算法求解，必须证明每一步所作的贪心选择最终导致问题的整体最优解。证明的大致过程为：首先考察问题的一个整体最优解，并证明可修改这个最优解，使其以贪心选择开始，做了贪心选择后，原问题简化为规模更小的类似子问题。然后用数学归纳法证明通过每一步做贪心选择，最终可得到问题的整体最优解。

存在问题

贪心算法也存在如下问题：

1. 不能保证解是最佳的。因为贪心算法总是从局部出发，并没从整体考虑；
2. 贪心算法一般用来解决求最大或最小解；
3. 贪心算法只能确定某些问题的可行性范围

经典例题

买卖股票的最佳时机 II

给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。

在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。

返回 你能获得的 最大 利润 。
示例 1：

输入：prices = [7,1,5,3,6,4]
输出：7
解释：在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 =5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3 。总利润为 4 + 3 = 7 。

示例 2：

输入：prices = [1,2,3,4,5]
输出：4
解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。总利润为 4 。

示例 3：

输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 交易无法获得正利润，所以不参与交易可以获得最大利润，最大利润为 0 。

提示：

• 1 <= prices.length <= 3 * 104
• 0 <= prices[i] <= 104

解决方案

由于股票的购买没有限制，因此整个问题等价于寻找 $x$ 个不相交的区间 (li,ri](l_i,r_i](li​,ri​] 使得如下的等式最大化

其中 lil_ili​ 表示在第 lil_ili​ 天买入，rir_iri​ 表示在第 rir_iri​ 天卖出。

同时我们注意到对于 (li,ri](l_i,r_i](li​,ri​] 这一个区间贡献的价值 a[ri]−a[li]a[r_i]-a[l_i]a[ri​]−a[li​]，其实等价于 (li,li+1],(li+1,li+2],…,(ri−1,ri](l_i,l_i+1],(l_i+1,l_i+2],\ldots,(r_i-1,r_i](li​,li​+1],(li​+1,li​+2],…,(ri​−1,ri​] 这若干个区间长度为 $1$ 的区间的价值和，即

a[ri]−a[li]=(a[ri]−a[ri−1])+(a[ri−1]−a[ri−2])+…+(a[li+1]−a[li])a[r_i]-a[l_i]=(a[r_i]-a[r_i-1])+(a[r_i-1]-a[r_i-2])+\ldots+(a[l_i+1]-a[l_i]) a[ri​]−a[li​]=(a[ri​]−a[ri​−1])+(a[ri​−1]−a[ri​−2])+…+(a[li​+1]−a[li​])

因此问题可以简化为找 $x$ 个长度为 $1$ 的区间 (li,li+1](l_i,l_i+1](li​,li​+1] 使得 ∑i=1xa[li+1]−a[li]\sum_{i=1}^{x} a[l_i+1]-a[l_i]∑i=1x​a[li​+1]−a[li​] 价值最大化。

贪心的角度考虑我们每次选择贡献大于 00 的区间即能使得答案最大化，因此最后答案为

其中 nn 为数组的长度。

需要说明的是，贪心算法只能用于计算最大利润，计算的过程并不是实际的交易过程。

考虑题目中的例子 [1,2,3,4,5][1,2,3,4,5]，数组的长度 n=5n=5，由于对所有的 1≤ia[i−1]，因此答案为

但是实际的交易过程并不是进行 44 次买入和 44 次卖出，而是在第 11 天买入，第 55 天卖出。

class Solution {
    public int maxProfit(int[] prices) {
        int ans = 0;
        int n = prices.length;
        for (int i = 1; i < n; ++i) {
            ans += Math.max(0, prices[i] - prices[i - 1]);
        }
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10

复杂度分析

• 时间复杂度：O(n)O(n)，其中 nn 为数组的长度。我们只需要遍历一次数组即可。
• 空间复杂度：O(1)O(1)。只需要常数空间存放若干变量。

来源

122. 买卖股票的最佳时机 II
贪心算法