讀完本文，你可以去力扣拿下如下題目：
-----------
這是 LeetCode 第 855 題，有趣且具有一定技巧性。這種題目并不像動(dòng)態(tài)規(guī)劃這類算法拼智商，而是看你對(duì)常用數(shù)據(jù)結(jié)構(gòu)的理解和寫代碼的水平，個(gè)人認(rèn)為值得重視和學(xué)習(xí)。
另外說句題外話，很多讀者都問，算法框架是如何總結(jié)出來的，其實(shí)框架反而是慢慢從細(xì)節(jié)里摳出來的。希望大家看了我們的文章之后，最好能抽時(shí)間把相關(guān)的問題親自做一做，紙上得來終覺淺，絕知此事要躬行嘛。
先來描述一下題目：假設(shè)有一個(gè)考場(chǎng)，考場(chǎng)有一排共 N 個(gè)座位，索引分別是 [0..N-1]，考生會(huì)陸續(xù)進(jìn)入考場(chǎng)考試，并且可能在任何時(shí)候離開考場(chǎng)。
PS：我認(rèn)真寫了 100 多篇原創(chuàng)，手把手刷 200 道力扣題目，全部發(fā)布在 labuladong的算法小抄，持續(xù)更新。建議收藏，按照我的文章順序刷題，掌握各種算法套路后投再入題海就如魚得水了。
你作為考官，要安排考生們的座位，滿足：每當(dāng)一個(gè)學(xué)生進(jìn)入時(shí)，你需要最大化他和最近其他人的距離；如果有多個(gè)這樣的座位，安排到他到索引最小的那個(gè)座位。這很符合實(shí)際情況對(duì)吧，
也就是請(qǐng)你實(shí)現(xiàn)下面這樣一個(gè)類：
class ExamRoom {
// 構(gòu)造函數(shù)，傳入座位總數(shù) N
public ExamRoom(int N);
// 來了一名考生，返回你給他分配的座位
public int seat();
// 坐在 p 位置的考生離開了
// 可以認(rèn)為 p 位置一定坐有考生
public void leave(int p);
}
比方說考場(chǎng)有 5 個(gè)座位，分別是 [0..4]：
第一名考生進(jìn)入時(shí)（調(diào)用 seat()），坐在任何位置都行，但是要給他安排索引最小的位置，也就是返回位置 0。
第二名學(xué)生進(jìn)入時(shí)（再調(diào)用 seat()），要和旁邊的人距離最遠(yuǎn)，也就是返回位置 4。
第三名學(xué)生進(jìn)入時(shí)，要和旁邊的人距離最遠(yuǎn)，應(yīng)該做到中間，也就是座位 2。
如果再進(jìn)一名學(xué)生，他可以坐在座位 1 或者 3，取較小的索引 1。
以此類推。
剛才所說的情況，沒有調(diào)用 leave 函數(shù)，不過讀者肯定能夠發(fā)現(xiàn)規(guī)律：
如果將每?jī)蓚€(gè)相鄰的考生看做線段的兩端點(diǎn)，新安排考生就是找最長(zhǎng)的線段，然后讓該考生在中間把這個(gè)線段「二分」，中點(diǎn)就是給他分配的座位。leave(p) 其實(shí)就是去除端點(diǎn) p，使得相鄰兩個(gè)線段合并為一個(gè)。
核心思路很簡(jiǎn)單對(duì)吧，所以這個(gè)問題實(shí)際上實(shí)在考察你對(duì)數(shù)據(jù)結(jié)構(gòu)的理解。對(duì)于上述這個(gè)邏輯，你用什么數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn)呢？
一、思路分析
根據(jù)上述思路，首先需要把坐在教室的學(xué)生抽象成線段，我們可以簡(jiǎn)單的用一個(gè)大小為 2 的數(shù)組表示。
另外，思路需要我們找到「最長(zhǎng)」的線段，還需要去除線段，增加線段。
但凡遇到在動(dòng)態(tài)過程中取最值的要求，肯定要使用有序數(shù)據(jù)結(jié)構(gòu)，我們常用的數(shù)據(jù)結(jié)構(gòu)就是二叉堆和平衡二叉搜索樹了。二叉堆實(shí)現(xiàn)的優(yōu)先級(jí)隊(duì)列取最值的時(shí)間復(fù)雜度是 O(logN)，但是只能刪除最大值。平衡二叉樹也可以取最值，也可以修改、刪除任意一個(gè)值，而且時(shí)間復(fù)雜度都是 O(logN)。
綜上，二叉堆不能滿足 leave 操作，應(yīng)該使用平衡二叉樹。所以這里我們會(huì)用到 Java 的一種數(shù)據(jù)結(jié)構(gòu) TreeSet，這是一種有序數(shù)據(jù)結(jié)構(gòu)，底層由紅黑樹維護(hù)有序性。
這里順便提一下，一說到集合（Set）或者映射（Map），有的讀者可能就想當(dāng)然的認(rèn)為是哈希集合（HashSet）或者哈希表（HashMap），這樣理解是有點(diǎn)問題的。
因?yàn)楣＜?映射底層是由哈希函數(shù)和數(shù)組實(shí)現(xiàn)的，特性是遍歷無固定順序，但是操作效率高，時(shí)間復(fù)雜度為 O(1)。
而集合/映射還可以依賴其他底層數(shù)據(jù)結(jié)構(gòu)，常見的就是紅黑樹（一種平衡二叉搜索樹），特性是自動(dòng)維護(hù)其中元素的順序，操作效率是 O(logN)。這種一般稱為「有序集合/映射」。
我們使用的 TreeSet 就是一個(gè)有序集合，目的就是為了保持線段長(zhǎng)度的有序性，快速查找最大線段，快速刪除和插入。
PS：我認(rèn)真寫了 100 多篇原創(chuàng)，手把手刷 200 道力扣題目，全部發(fā)布在 labuladong的算法小抄，持續(xù)更新。建議收藏，按照我的文章順序刷題，掌握各種算法套路后投再入題海就如魚得水了。
二、簡(jiǎn)化問題
首先，如果有多個(gè)可選座位，需要選擇索引最小的座位對(duì)吧？我們先簡(jiǎn)化一下問題，暫時(shí)不管這個(gè)要求，實(shí)現(xiàn)上述思路。
這個(gè)問題還用到一個(gè)常用的編程技巧，就是使用一個(gè)「虛擬線段」讓算法正確啟動(dòng)，這就和鏈表相關(guān)的算法需要「虛擬頭結(jié)點(diǎn)」一個(gè)道理。
// 將端點(diǎn) p 映射到以 p 為左端點(diǎn)的線段
private Map<Integer, int[]> startMap;
// 將端點(diǎn) p 映射到以 p 為右端點(diǎn)的線段
private Map<Integer, int[]> endMap;
// 根據(jù)線段長(zhǎng)度從小到大存放所有線段
private TreeSet<int[]> pq;
private int N;
public ExamRoom(int N) {
this.N = N;
startMap = new HashMap<>();
endMap = new HashMap<>();
pq = new TreeSet<>((a, b) -> {
// 算出兩個(gè)線段的長(zhǎng)度
int distA = distance(a);
int distB = distance(b);
// 長(zhǎng)度更長(zhǎng)的更大，排后面
return distA - distB;
});
// 在有序集合中先放一個(gè)虛擬線段
addInterval(new int[] {-1, N});
}
/* 去除一個(gè)線段 */
private void removeInterval(int[] intv) {
pq.remove(intv);
startMap.remove(intv[0]);
endMap.remove(intv[1]);
}
/* 增加一個(gè)線段 */
private void addInterval(int[] intv) {
pq.add(intv);
startMap.put(intv[0], intv);
endMap.put(intv[1], intv);
}
/* 計(jì)算一個(gè)線段的長(zhǎng)度 */
private int distance(int[] intv) {
return intv[1] - intv[0] - 1;
}
「虛擬線段」其實(shí)就是為了將所有座位表示為一個(gè)線段：
有了上述鋪墊，主要 API seat 和 leave 就可以寫了：
public int seat() {
// 從有序集合拿出最長(zhǎng)的線段
int[] longest = pq.last();
int x = longest[0];
int y = longest[1];
int seat;
if (x == -1) { // 情況一
seat = 0;
} else if (y == N) { // 情況二
seat = N - 1;
} else { // 情況三
seat = (y - x) / 2 + x;
}
// 將最長(zhǎng)的線段分成兩段
int[] left = new int[] {x, seat};
int[] right = new int[] {seat, y};
removeInterval(longest);
addInterval(left);
addInterval(right);
return seat;
}
public void leave(int p) {
// 將 p 左右的線段找出來
int[] right = startMap.get(p);
int[] left = endMap.get(p);
// 合并兩個(gè)線段成為一個(gè)線段
int[] merged = new int[] {left[0], right[1]};
removeInterval(left);
removeInterval(right);
addInterval(merged);
}
至此，算法就基本實(shí)現(xiàn)了，代碼雖多，但思路很簡(jiǎn)單：找最長(zhǎng)的線段，從中間分隔成兩段，中點(diǎn)就是 seat() 的返回值；找 p 的左右線段，合并成一個(gè)線段，這就是 leave(p) 的邏輯。
PS：我認(rèn)真寫了 100 多篇原創(chuàng)，手把手刷 200 道力扣題目，全部發(fā)布在 labuladong的算法小抄，持續(xù)更新。建議收藏，按照我的文章順序刷題，掌握各種算法套路后投再入題海就如魚得水了。
三、進(jìn)階問題
但是，題目要求多個(gè)選擇時(shí)選擇索引最小的那個(gè)座位，我們剛才忽略了這個(gè)問題。比如下面這種情況會(huì)出錯(cuò)：
現(xiàn)在有序集合里有線段 [0,4] 和 [4,9]，那么最長(zhǎng)線段 longest 就是后者，按照 seat 的邏輯，就會(huì)分割 [4,9]，也就是返回座位 6。但正確答案應(yīng)該是座位 2，因?yàn)?2 和 6 都滿足最大化相鄰考生距離的條件，二者應(yīng)該取較小的。
遇到題目的這種要求，解決方式就是修改有序數(shù)據(jù)結(jié)構(gòu)的排序方式。具體到這個(gè)問題，就是修改 TreeMap 的比較函數(shù)邏輯：
pq = new TreeSet<>((a, b) -> {
int distA = distance(a);
int distB = distance(b);
// 如果長(zhǎng)度相同，就比較索引
if (distA == distB)
return b[0] - a[0];
return distA - distB;
});
除此之外，還要改變 distance 函數(shù)，不能簡(jiǎn)單地讓它計(jì)算一個(gè)線段兩個(gè)端點(diǎn)間的長(zhǎng)度，而是讓它計(jì)算該線段中點(diǎn)和端點(diǎn)之間的長(zhǎng)度。
private int distance(int[] intv) {
int x = intv[0];
int y = intv[1];
if (x == -1) return y;
if (y == N) return N - 1 - x;
// 中點(diǎn)和端點(diǎn)之間的長(zhǎng)度
return (y - x) / 2;
}
這樣，[0,4] 和 [4,9] 的 distance 值就相等了，算法會(huì)比較二者的索引，取較小的線段進(jìn)行分割。到這里，這道算法題目算是完全解決了。
四、最后總結(jié)
本文聊的這個(gè)問題其實(shí)并不算難，雖然看起來代碼很多。核心問題就是考察有序數(shù)據(jù)結(jié)構(gòu)的理解和使用，來梳理一下。
處理動(dòng)態(tài)問題一般都會(huì)用到有序數(shù)據(jù)結(jié)構(gòu)，比如平衡二叉搜索樹和二叉堆，二者的時(shí)間復(fù)雜度差不多，但前者支持的操作更多。
既然平衡二叉搜索樹這么好用，還用二叉堆干嘛呢？因?yàn)槎娑训讓泳褪菙?shù)組，實(shí)現(xiàn)簡(jiǎn)單啊，詳見舊文「二叉堆詳解」。你實(shí)現(xiàn)個(gè)紅黑樹試試？操作復(fù)雜，而且消耗的空間相對(duì)來說會(huì)多一些。具體問題，還是要選擇恰當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)來解決。
希望本文對(duì)大家有幫助。
＿＿＿＿＿＿＿＿＿＿＿＿＿
我的 在線電子書 有 100 篇原創(chuàng)文章，手把手帶刷 200 道力扣題目，建議收藏！對(duì)應(yīng)的 GitHub 算法倉庫 已經(jīng)獲得了 70k star，歡迎標(biāo)星！
