LeetCode演算法題-Maximize Distance to Closest Person（Java實現）
這是悅樂書的第328 次更新，第351 篇原創
01 看題和準備
今天介紹的是LeetCode演算法題中Easy級別的第198題（順位題號是849）。在一排座位中，1表示一個人坐在該座位上，0表示座位是空的。在這些座位中，至少有一個空座位，至少有一個人坐著。Alex想坐在座位上，以便他和離他最近的人之間的距離最遠。返回距離最近的人的最大距離。例如：
輸入：[1,0,0,0,1,0,1]
輸出：2
說明：如果Alex坐在第二個空座位（seats[2]），那麼離最近的人距離為2。如果Alex坐在任何其他空座位上，則離最近的人的距離為1。因此，到最近的人的最大距離是2。
輸入：[1,0,0,0]
輸出：3
說明：如果Alex坐在最後一個座位上，那麼離他最近的人距離為3。這是可能的最大距離，所以答案是3。
注意：
-
1 <= seats.length <= 20000
-
所有座位中僅包含0或1，至少一個0，至少一個1。
本次解題使用的開發工具是eclipse，jdk使用的版本是1.8，環境是win7 64位系統，使用Java語言編寫和測試。
02 解題
在解題前，先來看看題目的意思。Alex想要在一排座位中，找到一個離人最近但是距離最遠的座位，題目通過一個數組來表示一排座位，元素值為0表示當前這個座位是空的，Alex可以坐，為1時表示當前這個座位有人坐了，Alex不能坐，也就是說，在為0的座位中，要找一個離最近的人距離越遠越好的座位。我們可以分三種情況來選座位：
（1）左邊是牆時，即陣列中第一個元素是0，或者陣列前部分是連續的0，如果往右，至少會遇到一個座位上有人，此時Alex離這個人是最近的，距離也是最遠的。比如陣列{0,0,0,1}，Alex坐在第一個座位上，離他最近的人的最遠距離是3。
（2）左右兩邊都有人時，即此時陣列中出現了一段連續的0，也就是有連續好幾個連著的空座位可以選，此時Alex坐在這些連續空座位的中間是最好的，離左右兩邊的人最近，距離也是相等的。比如陣列{1,0,0,0,1}，Alex坐在第三個座位上，即坐在seats[2]上，距離兩邊的人都是最近的，且距離最大，都為2。
（3）右邊是牆時，即陣列中最後一個元素是0，或者後部分是連續的0，如果往左，至少會遇到一個座位上有人，此時Alex離這個人是最近的，距離也是最遠的。比如陣列{1,0,0,0}，Alex坐在第四個座位上，離他最近的人的最遠距離是3。
通過上面的分析，我們可以使用一個變數記錄前一個座位已經被坐的索引，再根據當前座位來判斷，看屬於上面三種情況中的哪一種，計算距離，比較最大值，通過雙指標來實現。
注意，計算距離是計算索引之差。
public int maxDistToClosest(int[] seats) {
int left = -1, n = seats.length;
int maxDistance = 0;
for (int i=0; i<n; i++) {
if (seats[i] == 0) {
continue;
}
if (left == -1) {
// 左邊第一位是1或者連續的0，有可能左邊靠牆
maxDistance = Math.max(maxDistance, i);
} else {
// 中間部分連續的0，即中間
maxDistance = Math.max(maxDistance, (i-left)/2);
}
left = i;
}
// 結束部分為連續的0，即右邊靠牆
if (seats[n-1] == 0) {
maxDistance = Math.max(maxDistance, n-1-left);
}
return maxDistance;
}
03 小結
演算法專題目前已日更超過五個月 ，演算法題文章198 +篇，公眾號對話方塊回覆【資料結構與演算法 】、【演算法 】、【資料結構 】中的任一關鍵詞，獲取系列文章合集。
以上就是全部內容，如果大家有什麼好的解法思路、建議或者其他問題，可以下方留言交流，點贊、留言、轉發就是對我最大的回報和支援！