[LeetCode] 849. Maximize Distance to Closest Person

轉自LeetCode

In a row of seats, 1 represents a person sitting in that seat, and 0 represents that the seat is empty. 

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 closest person.

Example 1:

Input: [1,0,0,0,1,0,1]
Output: 2
Explanation: 
If Alex sits in the second open seat (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: [1,0,0,0]
Output: 3
Explanation: 
If Alex sits in the last seat, the closest person is 3 seats away.
This is the maximum distance possible, so the answer is 3.

Note:

1. 1 <= seats.length <= 20000
2. seats contains only 0s or 1s, at least one 0, and at least one 1.

<Solution>

想法如下

• 先檢查每個可坐的位置，在它的左邊，離它最近的距離

• 再檢查每個可坐的位置，在它的右邊，離它最近的距離，並且和左邊的距離取最小值。過程中，同時紀錄整體最大值是多少

• 要注意的地方是，如果左邊或右邊的都是空位，那麼紀錄的值要夠大，這樣之後取最小值的時候，才能得到對的值

code 如下

Java