前幾天，有一哥們發我一個LeetCode題目連結，緊跟著附上了自己的提交記錄，一個2ms，另一個1451ms...
我一看，這題有點意思啊，不同的思路竟然時間差這麼多。搞它。
題目描述這裡有n個航班，它們分別從1到n進行編號。
我們這兒有一份航班預訂表，表中第i條預訂記錄bookings[i] = [i, j, k]意味著我們在從i到j的每個航班上預訂了k個座位。
請你返回一個長度為n的數組answer，按航班編號順序返回每個航班上預訂的座位數。
示例：
❝輸入：bookings = [ [1,2,10], [2,3,20], [2,5,25] ], n = 5
輸出：[10,55,45,25,25]
❞O(m*n)解法根據題意初始化長度為n的answer數組，代表1到n號航班預訂的座位數量，外層遍歷 bookings，內層遍歷bookings[i] = [i, j, k]，計算航班號i到j的座位數量，即當前座位數量加k。
public int[] corpFlightBookings(
int[][] bookings, int n) {
int[] answer = new int[n];
// 遍歷整個bookings數組
for (int[] b : bookings) {
// 內層循環把每個航班預訂數加上
for (int i = b[0] - 1;
i <= b[1] - 1; i++) {
answer[i] += b[2];
}
}
return answer;
}
O(n)解法思考O(m*n)解法中關鍵一點，內層循環我們一直重複的在[i, j]之間加上k，怎麼將這循環變成O(1)，成為問題的關鍵！
[i, j]之間加上k，這讓我想到了等差數列，這不就是公差為k的等差數列嗎？然後呢？
分析設answer[i]表示第i個航班預訂的座位數。定義一個差分數組d[]，d[i]表示第i個航班與第i-1個航班預訂座位的差值，即d[i] = answer[i] - answer[i - 1]。
這樣，我們每次遍歷到bookings[i] = [i, j, k]，就只需要將d[i]增加k，d[j + 1]減少k即可，因為i到j之間，航班預訂數量是沒有變化的。
最後，計算answer[i] = answer[i - 1] + d[i]，返回answer即可。
推演好吧，這樣說可能有人沒懂，我們按照題目的例子推演一次：
初始航班預訂數量數組 answer = [0,0,0,0,0]，差分數組d = [0,0,0,0,0]當遍歷到bookings[0] = [1,2,10]的時候，差分數組第1位加10，第3位減10，變成d = [10,0,-10,0,0]同理，當遍歷到bookings[1] = [2,3,20]的時候，差分數組變成d = [10,20,-10,-20,0]當遍歷到bookings[2] = [2,5,25]的時候，差分數組變成d = [10,45,-10,-20,0]，第6位要減25，我們也不需要了最後計算answer數組的值，answer[0] = d[0] = 10，answer[1] = d[1] + answer[0] = 45 + 10 = 55，answer[2] = d[2] + answer[1] = -10 + 55 = 45...最最後發現，只申請一個數組表示d[]和answer[]就可以了，over！代碼public int[] corpFlightBookings(
int[][] bookings, int n) {
int[] answer = new int[n];
// 遍歷bookings 計算航班i+1 對航班i 變化的預訂數
for (int[] b : bookings) {
// 增加的預訂數
answer[b[0] - 1] += b[2];
// 防止數組越界
if (b[1] < n) {
// 減少的預訂數量
answer[b[1]] -= b[2];
}
}
// 航班i的預訂數等於,i-1的預訂數，加i時刻變化的預定數
for (int i = 1; i < n; i++) {
answer[i] += answer[i - 1];
}
return answer;
}
拼車❝你以為這就完了嗎？不要太天真。再來看一下這個題，或許會給你帶來新思路。
❞題目描述假設你是一位順風車司機，車上最初有 capacity 個空座位可以用來載客。由於道路的限制，車 只能 向一個方向行駛（也就是說，不允許掉頭或改變方向，你可以將其想像為一個向量）。
這兒有一份行程計劃表 trips[][]，其中 trips[i] = [num_passengers, start_location, end_location] 包含了你的第 i 次行程信息：
必須接送的乘客數量；乘客的上車地點；以及乘客的下車地點。這些給出的地點位置是從你的 初始 出發位置向前行駛到這些地點所需的距離（它們一定在你的行駛方向上）。
請你根據給出的行程計劃表和車子的座位數，來判斷你的車是否可以順利完成接送所用乘客的任務（若且唯若你可以在所有給定的行程中接送所有乘客時，返回 true，否則請返回 false）。
示例 1：
❝輸入：trips = [[2,1,5],[3,3,7]], capacity = 4
輸出：false
❞示例 2：
❝輸入：trips = [[2,1,5],[3,3,7]], capacity = 5
輸出：true
❞提示：
你可以假設乘客會自覺遵守 「先下後上」 的良好素質題目分析這道題實際上就是問，車的座位數量是否能滿足每個行程i的乘客，即每個乘客都坐上座位，能則返回true，否則返回false。
如果我們能計算出，行程i，要乘車的乘客的數量，然後跟capacity對比一下，就能得到答案了。
很顯然，「要乘車的乘客的數量 = 車上原來乘客的數量 - 下車乘客數量 + 上車乘客數量」。
思路我們可以用數組或者Map記錄，行程i，下車乘客的數量和上車乘客的數量，然後行程開始到結束，計算要乘車的乘客數量，並與capacity比較。
代碼實現Map版public boolean carPooling(
int[][] trips, int capacity) {
// 使用TreeMap 是為了讓元素根據key排序
TreeMap<Integer, Integer> map =
new TreeMap<>();
for (int[] t : trips) {
int v = map.getOrDefault(t[1], 0) + t[0];
// 上車乘客數量
map.put(t[1], v);
v = map.getOrDefault(t[2], 0) - t[0];
// 下車乘客數量
map.put(t[2], v);
}
int cur = 0;
for (Map.Entry<Integer, Integer> entry
: map.entrySet()) {
Integer value = entry.getValue();
// 當前數量=之前數量+變化的數量
cur += value;
if (cur > capacity) {
return false;
}
}
return true;
}
代碼實現數組版public boolean carPooling(
int[][] trips, int capacity) {
// 最遠行程 數組長度
int max = 0;
for (int[] t : trips) {
max = Math.max(max, t[2]);
}
// 所有要乘車的乘客數量
int[] passengers = new int[max + 1];
for (int[] t : trips) {
passengers[t[1]] += t[0];
passengers[t[2]] -= t[0];
}
int cur = 0;
for (int passenger : passengers) {
// 當前數量 = 之前數量 + 變化的數量
cur += passenger;
if (cur > capacity) {
return false;
}
}
return true;
}
回頭「拼車」的代碼與場景感覺好理解一些，因為生活中我們就是這樣，先下後上，能不能坐上座，就看車上原來有多少人，還有下車多少人。
我們再回來來看「航班預訂統計」這題，實際上跟「拼車」是完全一樣的題目。
我看到有人問，計算bookings[i] = [i, j, k]預訂變化數量的時候，為啥是第j + 1的位置要減k，而不是j的位置呢？因為，j - 1的位置，航班預訂座位數量應該加k，而j的位置，航班預訂座位數量也加k，所以j和j - 1之間數量是沒有變化的。但是，j + 1的位置航班數量不再加k了，所以j + 1相對於j位置航班預訂數量是減少k的。
而「拼車」這道題，trips[i][j]，在j位置，車到站了，乘客就下車了，再坐一站就過站了...
總之，兩道題本質是完全一樣的，只不過略微有些細節不同。