leetcode小结——贪心算法

最近刷题策略有些改变，从难度分类更改为题型分类，正好贪心算法类型的题刷完了，就在这里小结一下心得。之后每刷完一类题型也会记录，打算写成一个系列。

原理

在进入贪心算法的细节之前，或者说进入这一算法系列博文之前，必须先思考一个问题：算法的本质究竟是什么？

我倾向于将无法在短时间解决的大问题分成有条理有规则的小问题去依次解决，比如学算法，就按类型依次攻破。那么是依照什么原则将算法进行分类的呢？我相信既然统称为算法，那自然是有可提取的共性，而每一类算法又肯定是有其特性，由此可得对于同一类算法，应该是可以依据所有算法的共性，来抽象出一种针对其特性的通用思考方法来解决，做到举一反三。

之后的所有实例我也会尝试以这样的思考方式去写出解题思路。题不在多，能足够记录出某一类算法其基于共性的特性思维方式即可。

共性

现在我们讨论的都是计算机算法，就是用计算机能够执行有限步步骤解决某一个问题。那么计算机是依靠什么解决问题的呢？我的理解是这样，计算机的本质就是一个状态机，其储存的所有数据就构成了当前的状态。当我们用计算机解决算法问题时，其实就是经历了如下几步：

1. 将这个问题定义为计算机可以表达的状态（变量存储数据，这些数据能够表达算法结果）
2. 定义初始状态（根据已知条件初始化相关变量）
3. 实现状态间的转移（根据初始变量计算出中间状态，根据中间状态持续转移）
4. 获取最终状态（得到能够表达算法最终结果的数据）

可以说每个算法无论简单还是复杂，都可以抽象为如上4步。不同算法的特性关键就在于第3步，如何实现状态间的转移。不妨再从头理一理。首先，我们需要用一个算法解决一个问题，这个问题可以依据自己的理解定义为计算机的状态。问题必然有已知条件，这个条件可以被定义为算法的初始状态。问题的结果就是我们需要的最终状态。很显然，大多数问题并不是1+1=2，我们不能简单的从初始状态直接推算到最终状态，那么就需要从初始状态推断出中间状态，然后根据中间状态继续推断，得出最终状态。从初始状态推断出中间状态的过程，就是状态转移，也就是算法核心。

举个例子，现在有50X50的一个棋盘，要从左下角走到右上角，每次走一格，求出最短路径所需步数。这个问题定义为状态的话，就是需要用变量保存当前位置和已经走过的步骤数。初始状态就是（0,0）和0，当然状态的定义依据个人理解可以有不一样，不过无论如何都需要描述出这个问题，并且最终状态能够解决这个问题。

显然我们不能由初始状态直接得到最终状态，但别忘了题目的条件，转化为状态即为坐标每加1，步骤数就需要加1。这一步就是状态的转移。每一次转移，我们都能得到一个中间状态，而中间状态的一步步转移，就能得到最终状态了。但坐标现在有两个，加1可以加在x上也可以加在y上，可以看到，即使是这样一个简单的问题，初始状态推算出的中间状态也有多种，复杂问题可以会存在无数的中间状态，甚至某一个中间状态需要之前多个中间状态共同决定。幸运的是，有些问题只需要这些无数中间状态的其中几种或者一种，就能推算出后续中间状态，我称这些被选择的中间状态为最优中间状态。

如何针对特定问题获取最优中间状态，就是不同算法的核心了。为了便于理解，中间状态又可以回退为子问题的最终状态，所以说一个复杂问题的算法解决具体思维流程可以概括如下：

1. 问题分割为可以用中间状态表达的若干子问题。
2. 定义合理的状态转移步骤从初始状态得到第一个子问题的最优中间状态。
3. 根据新获取的中间状态持续转移状态直至获取最后一个子问题的最终状态。

贪心算法特性

有了以上对于共性的理解，我们就可以针对特定算法按思路逐一分析了。

贪心算法，顾名思义，就是在每一次状态转移过程中，虽然有许多中间状态，但最优中间状态可以由上一次转移的最优中间状态直接得到。也就是说在求解当前子问题的解时，所需条件除了初始状态外，只要上一个子问题的解即可。

下面就从一些实例按此思路分析。

实例

402.Remove K Digits

题意为给定一个非负整数字符串和一个k值，需要从非负整数字符串中移除k个数字使得新数为最小。

例子如下：

Input: num = "1432219", k = 3
Output: "1219"
Explanation: Remove the three digits 4, 3, and 2 to form the new number 1219 which is the smallest.

由已知条件可以得出，最终状态为移除k个数字后的字符串。由于js中处理不同位数的增删用数组比较方便，所以我可以先确定最终状态为一个长度为num.length - k的数组，很自然的最初状态就为一个空数组。确认了最初状态和最终状态的基本结构，就可以分析如何实现状态转移了。 首先，数字大小的比较一定是从高位比到低位，要想数字更小，那么高位就要尽可能小。换句话说，由于现在我们只能实现移除操作，那么每一次移除操作中，位数字的变化只能是由下一位取代。如果下一位比被移除的位数小，这次移除才算最优，如果位数字严格递增的话则移除末尾的较大数字。

每一次移除可以看做一次状态转移并获得中间状态，最优中间状态肯定是按照上述条件去选择移除数字了，该问题也可以将每一次的移除分解为一个子问题，第k+1次状态转移只需要在k次所获得的最优解上执行即可，贪心算法即可解决该问题。解法如下：

var removeKdigits = function(num, k) {
  let stack = [], numDigits = num.length; // 初始状态表达
  for (let i = 0; i < numDigits; i++) {
    while(k > 0 && stack.length && stack[stack.length - 1] > num[i]) {
        stack.pop();  // 每一次满足while条件时执行一次最优状态转移，获取第k个子问题的解
        k--;
    }
    stack.push(num[i]);
  }
  // 中间状态已满足严格递增时，剩余子问题按末尾移除
  stack = k > 0 ? stack.slice(0, -k) : stack;
  // 最终状态已获取，按题意转化
  return stack.join('').replace(/^0+/, '') || '0';
};

55.Jump Game

题意为给出一个非负整数数组，每一个元素代表最大前进步数，初始位置为0，求出是否能达到最末位。

例子如下：

Input: [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

很显然，这一题的最终状态可以设置为最终到达索引位置，最初状态则为0，代表着最初位置。目标很明确，每一次状态转移的最优中间状态让索引位置尽可能的大即可，第k+1次最优中间状态是由第k次最优中间状态代表的子数组计算出，如果第k+1次的最优中间状态不能超过第k次或者超过了数组长度则代表着完成最终状态的转移。

由于每次状态转移所需条件仅为上一次的最优中间状态，所以贪心算法可解：

var canJump = function(nums) {
    let max = 0; // 初始状态表达
    for (let i = 0; i < nums.length && i <= max;i++) {
        max = Math.max(nums[i] + i, max); // 每一次满足条件时执行状态转移，直至获取最终状态
    }
    return max >= nums.length - 1; // 最终状态已获取，按题意转化
};

小结

实际上每一个特定的题目，定义状态的方法各种各样，根据不同的状态分析解法也可能会有不同的算法思路。贪心算法可能有大部分问题都无法解决，毕竟只是计算了局部最优解并根据其推导出全局最优，但相对的，由于维护的状态少，只要贪心策略能在某一问题下被证明有效，其实现的简洁性也会优于大部分算法。