[leetcode]1109. 航班預訂統計（擊敗100%用戶演算法-差分數組的詳解）

• 2021 年 9 月 1 日
• 筆記
• leetcode

執行用時2ms，擊敗100%用戶
記憶體消耗52.1MB,擊敗91%用戶

這也是我第一次用差分數組，之前從來沒有碰到過，利用差分數組就是利用了差分數組在某一區間內同時加減情況，只會改變最左邊和最右邊+1的位置上的值。區間最左邊同步加減，區間最右邊同步加減其相反數。
例如有一原始數組為[2,5,4,7,10,1]
獲得的差分數組為[2,3,-1,3,3,-9]

第一步：0-3區間的同步加6
則此時原始數組為[2+6,5+6,4+6,7+6,10,1]
獲得的差分數組為[2+6,3,-1,3,3-6,-9]

第二步：2-4區間的同步加3
則此時原始數組為[2+6,5+6,4+6+3,7+6+3,10+3,1]
獲得的差分數組為[2+6,3,-1+3,3,-3,-9-3]

可以看出其規律，差分數組對應d[i]=a[i]+a[i-1]
且如果在[m,n]區間同時相加x，那麼在差分數組內只有最左邊的邊緣a改變同步加減，即d[m]=a[m]+x-a[m-1]=(a[m]-a[m-1])+x=d[m]+x
而最右邊加了一個數，因為最右邊加一的位置會產生變化，即d[n]=a[n]-(a[n-1]+x)=d[n]-x

因此在此題中，只需將其初始化為0的差分數組，然後對應相加減即可。
普通未優化的差分數組

class Solution {
    public int[] corpFlightBookings(int[][] bookings, int n) {
        int [] anser = new int[n];
        for (int i=0;i<bookings.length;i++){
            anser[bookings[i][0]-1] +=bookings[i][2];
            if (bookings[i][1]<=n-1){
                anser[bookings[i][1]] -= bookings[i][2];
            }
        }

//        for (int i=1;i<n;i++){
//            anser[i]=anser[i]+anser[i-1];
//        }
        for (int i =0;i<n;i++){
            if (i==0){
            }else {
                anser[i]=anser[i]+anser[i-1];
            }
        }
        return anser;
    }
}

此時在while循環中需要大量的判斷，因此用空間換時間，新建差分數組是我們對留兩個，一個留給0的位置，一個留給n+1的位置，這樣邊間的處理也都在while循環中，結束後再進行重新的賦值，此時時間複雜度最低！

class Solution {
    public int[] corpFlightBookings(int[][] bookings, int n) {
        int [] anser = new int[n+2];
        int [] anser2 = new int[n];
        for (int i=0;i<bookings.length;i++){
            anser[bookings[i][0]] +=bookings[i][2];
            anser[bookings[i][1]+1] -= bookings[i][2];
        }

        for (int i =0;i<n;i++){
            anser[i+1] = anser[i]+anser[i+1];
        }
        for (int i=1;i<=n;i++){
            anser2[i-1]=anser[i];
        }
        return anser2;
    }
}