Last Updated on 2022-01-16 by Clay
題目
You are given an array representing a row of seats where seats[i] = 1 represents a person sitting in the ith seat, and seats[i] = 0 represents that the ith seat is empty (0-indexed). There is at least one empty seat, and at least one person sitting. Alex wants to sit in the seat such that the distance between him and the closest person to him is maximized. Return that maximum distance to the closest person.
Example 1:
Input: seats = [1,0,0,0,1,0,1] Output: 2 Explanation: If Alex sits in the second open seat (i.e. seats[2]), then the closest person has distance 2. If Alex sits in any other open seat, the closest person has distance 1. Thus, the maximum distance to the closest person is 2.
Example 2:
Input: seats = [1,0,0,0] Output: 3 Explanation: If Alex sits in the last seat (i.e. seats[3]), the closest person is 3 seats away. This is the maximum distance possible, so the answer is 3.
Example 3:
Input: seats = [0,1] Output: 1
Constraints:
2 <= seats.length <= 2 * 104seats[i]is0or1.- At least one seat is empty.
- At least one seat is occupied.
題目意思非常單純，給定一排座位的列表，如果列表中的元素為 0，則代表沒有人坐、反之若是 1，則代表已經有人坐了。
我們要做的，就是計算最遠能夠坐離他人幾個位子呢？
解題思路
這題看似簡單，其實有個小陷阱：如果沒有人的座位是從開頭開始計算、或是沒有人的座位結束在結尾，那麼我們只需要計算單方面的距離，亦即沒有人坐的位置數量等於實際距離。
然而，若是連續無人坐的位置開始與結束的左右兩端都有人座，那麼無人座（假設為 n 個）偶數的情況為 n / 2、無人座奇數的情況則為 n / 2 + 1：
XOOOOX
XOOOX
|-|
2
也就是說假設中間無人座的數量無論是 3 還是 4，實際上與人可以保持的間隔距離就是為 2。
我實際上寫程式的解法是先計算左邊開頭情況、再計算右邊結尾的情況，接著才是用上方公式計算中間排列的無人座情況。所以大致上分成三種情況、中間無人座的情況又要以奇偶數來決定不一樣的值。
實際情況就參考下方程式碼吧！
複雜度
| Time Complexity | O(n) |
| Space Complexity | O(1) |
C++ 範例程式碼
class Solution {
public:
int maxDistToClosest(vector<int>& seats) {
// Init
int l = 0;
int r = seats.size()-1;
int maxDist = 0;
int tempDist = 0;
// Left side
while (seats[l] == 0) {
++tempDist;
++l;
}
maxDist = max(maxDist, tempDist);
tempDist = 0;
// Right side
while (seats[r] == 0) {
++tempDist;
--r;
}
maxDist = max(maxDist, tempDist);
tempDist = 0;
for (int i=l; i<=r; ++i) {
if (seats[i] == 0) ++tempDist;
else tempDist = 0;
if (tempDist % 2 == 0) {
maxDist = max(maxDist, tempDist/2);
}
else {
maxDist = max(maxDist, tempDist/2+1);
}
}
return maxDist;
}
};Python 範例程式碼
class Solution:
def maxDistToClosest(self, seats: List[int]) -> int:
# Init
l = 0
r = len(seats) - 1
maxDist = 0
tempDist = 0
# Left side
while seats[l] == 0:
tempDist += 1
l += 1
maxDist = max(maxDist, tempDist)
tempDist = 0
# Right side
while seats[r] == 0:
tempDist += 1
r -= 1
maxDist = max(maxDist, tempDist)
tempDist = 0;
for i in range(l, r):
if seats[i] == 0: tempDist += 1
else: tempDist = 0
if tempDist % 2 == 0: maxDist = max(maxDist, tempDist//2)
else: maxDist = max(maxDist, tempDist//2+1)
return maxDist