【Lintcode】358. Tree Planning

题目地址：

https://www.lintcode.com/problem/treeplanning/description

给定一个数组 A A A，和一个正整数 d d d，要求在 A A A中删除尽可能少的数，使得剩余的数相邻两个数之差大于等于 d d d。问至少要删多少个。题目保证 A A A是严格单调递增的。

思路是贪心。用一个变量 x x x存当前遇到的数，一开始赋值为 A [ 0 ] A[0] A[0]，然后向后遍历，一旦遇到距离 d d d以内的数，就将其删去；否则更新 x x x为最新遇到的数。例如对于 ( 1 , 2 , 3 , 5 , 6 ) (1,2,3,5,6) (1,2,3,5,6)， d = 2 d=2 d=2的情形，先令 x = 1 x=1 x=1，然后从 A [ 1 ] = 2 A[1]=2 A[1]=2开始向后遍历，遇到 2 2 2的时候，就要将其删除，于是计数加 1 1 1，接着遇到 3 3 3，与 1 1 1距离大于等于了 2 2 2了，就更新 x = 3 x=3 x=3，然后遇到 5 5 5，也是ok的，则更新 x = 5 x=5 x=5，最后遇到 6 6 6，发现距离太小，删除之，计数再加 1 1 1。最后答案是 2 2 2。这个方法含义是，一旦遇到距离过小了，就将靠后的数删掉。

算法正确性证明：

首先证明一个很显然的引理。如果对于两个数组 A A A和 B B B，这两个数组满足 A ⊂ B A\subset B A⊂B，那么删除个数的最优解中， B B B的删除个数一定不少于 A A A的删除个数。因为对于 B B B的删除的数，我们可以从 A A A中删一样的，也能得到合法解，而从 A A A删的数绝不会多于从 B B B删的数，所以结论成立。接下来用数学归纳法。当 A A A长度为 1 1 1或者 2 2 2时结论显然正确。设 A A A长度大于等于 3 3 3。设最优解与贪心解删除的第一个不同的数是，最优解删了 A [ z ] A[z] A[z]，而贪心解删了 A [ t ] A[t] A[t]（这里隐含的前提是，如果贪心解删了数，最优解一定也会删，这个由上面贪心做法的原则知道，是显然的），贪心解删除的原则是遇到距离 d d d之内了才会删，因此有 z < t z< t z<t。当贪心解删了 A [ t ] A[t] A[t]之后，问题规模减少，而 A [ 0 : t − 1 ] A[0:t-1] A[0:t−1]已经满足条件了，由数学归纳法，后面继续用贪心法会得到一个最优解，而最优解删的是 A [ z ] A[z] A[z]， z z z在 t t t之前，所以贪心法得到的解的删除数量一定小于等于最优解之后的删除数量（因为由归纳假设，贪心得到的解就是最优解，然后由前面的引理，这个贪心最优解删除数一定少于最优解之后的删除数），综合起来，贪心解删除数小于等于最优解删除数，所以贪心解就是最优的。注意，这里的”最优“仅仅指删除数量最优，不是说删除的具体数是一致的。

代码如下：

public class Solution {
    /**
     * @param A: the positions of trees.
     * @param d: the minimum beautiful interval.
     * @return: the minimum number of trees to remove to make trees beautiful.
     */
    public int treePlanning(int[] A, int d) {
        // write your code here.
        int res = 0;
        // last就是上面解释中的x
        for (int i = 1, last = A[0]; i < A.length; i++) {
        	// 距离小于d，则删除A[i]
            if (A[i] - last < d) {
                res++;
            } else {
                last = A[i];
            }
        }
        
        return res;
    }
}
           

时间复杂度 O ( n ) O(n) O(n)，空间 O ( 1 ) O(1) O(1)。