P3102. 停车找车位

解题思路

题干中告知：至少停了一辆车在车位上，也至少有一个空位没有停车。说明输入的数组中至少有一个 1，也至少有一个 0，不会出现停车位全满或者全空的情况。

所停的车位有两种情况需要考虑：

• 左边没有车或者右边没有车，即停在边上的位置
• 左边和右边均有车，即停在两车之间

为了使得所停位置和最近的车距离最大，我们贪心地思考这个问题：

• 对于第一种停车情况，我们一定是停靠在最边上，才能使得本车距离其左边或右边最近的车最远
• 对于第二种停车情况，我们一定是恰好停在左右两车之间正中间的位置，才能使得本车距离左右两车的距离均远

有了以上贪心的思路，这道题就非常简单了：

1. 我们首先找到最左边的 1 和最右边的 1 的位置（索引），分别记为 left 和 right 2. 根据 left 和 right 计算按照第一种情况停车，能得到的最大距离，即 ans = max(left, n-1-right) 3. 然后遍历剩下的区间 lst[left+1:right+1]，每找到一个 1，就计算其位置 i 和上一个 1 的位置 pre 之间的距离的一半 (i-pre)//2，即为停在区间 lst[pre:i+1] 中的车，能取得的距离左右两辆车的最大距离，再将该结果和原先的 ans 比较并更新即可

另外，因为停车位最多 100 个，这个数据量很小，所以用暴力解肯定也是可以通过的。所谓暴力解，即对于所有 0，都去考虑其左边或右边的最近车位的距离，然后不断更新答案，这样的时间复杂度是 O(N²)，但是非常不推荐用这样的暴力解，因为一旦把数据量提上去就无法通过了，如果是面试时手撕代码遇到这样的题，面试官肯定也不满足你用暴力解的。