【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)。