每天一道算法題（航班預定-差分數組）

 乍一看這不很簡單嗎，循環first和last相加不就可以了嗎，兩分鐘搞出來：

public int[] corpFlightBookings(int[][] bookings, int n) {
        int[] bookSeats = new int[n] ;
        for(int[] book:bookings){
            for(int j = book[0]-1 ;j < book[1] ; j ++){
                bookSeats[j] += book[2] ;
            }
        }
        return bookSeats ;
    }
           

結果很殘酷：

看評論有一個大神，利用差分數組執行竟然隻需要2ms ，過程如下

加入有5個航班，先聲明一個差分數組：res[5]   ,有個預定為[2 ,4 , 40] 

那麼rest[1] - res[3] 都要加40  ，隻有res[0] 和res[4]不用加，

那麼我們就假設從下标1 開始後面全部加40 ，那麼隻需要差分數組res[1] + 10 即可，但是res[4]是不加的，并且如果後面還有後面也是不加的，那麼我們在res[4]-10 這樣後面的全部減了10 ，等于是抵消了前面的加 ,妙

public int[] corpFlightBookings(int[][] bookings, int n) {
        int[] res = new int[n];
        for (int[] booking : bookings) {
            res[booking[0] - 1] += booking[2];
            if (booking[1] < n) {
                res[booking[1]] -= booking[2];
            }
        }

        for (int i = 1; i < n; i++) {
            res[i] += res[i - 1];
        }

        return res;
    }