2023-08-22每日一題

一、題目編號

849. 到最近的人的最大距離

二、題目鏈接

點擊跳轉(zhuǎn)到題目位置

三、題目描述

給你一個數(shù)組 seats 表示一排座位，其中 seats[i] = 1 代表有人坐在第 i 個座位上，seats[i] = 0 代表座位 i 上是空的（下標從 0 開始）。

至少有一個空座位，且至少有一人已經(jīng)坐在座位上。

亞歷克斯希望坐在一個能夠使他與離他最近的人之間的距離達到最大化的座位上。

返回他到離他最近的人的最大距離。

示例 1：
示例2：

示例3：

提示：

• 2 <= seats.length <= 2 * 10⁴
• seats[i] 為 0 或 1
• 至少有一個 空座位
• 至少有一個 座位上有人

四、解題代碼

class Solution {
public:
    int maxDistToClosest(vector<int>& seats) {
        int dp1[20010];
        int dp2[20010];
        int max0 = 0;
        int n = seats.size();
        memset(dp1, 0, sizeof(dp1));
        memset(dp2, 0, sizeof(dp2));
        for(int i = 0; i < n; ++i){
            if(i == 0){
                if(seats[i]){
                    dp1[i] = 1;
                } else{
                    dp1[i] = 0;
                }
                continue;
            }
            if(seats[i]){
                dp1[i] = i + 1;
            } else{
                dp1[i] = dp1[i - 1];
            }
        }
        for(int i = n - 1; i >= 0; --i){
            if(seats[i]){
                dp2[i] = i + 1;
            } else{
                dp2[i] = dp2[i + 1];
            }
        }
        int len = 0;
        for(int i = 0; i < n; ++i){
            if(dp1[i] == i + 1 || dp2[i] == i + 1){
                continue;
            } else{
                int left = 0;
                int right = 0;
                if(dp1[i] == 0){
                    len = max(len, max(i + 1, dp2[i] - 1 - i));
                    continue;
                } else{
                    left = i + 1 - dp1[i];
                }
                if(dp2[i] == 0){
                    len = max(len, max(n - 1 - i, i + 1 - dp1[i]));
                    continue;
                } else{
                    right = dp2[i] - 1 - i;
                }
                len = max(len, min(left, right)); 
            }
        }
    return len;
    }
};

五、解題思路

(1) 可以用前后綴和來幫忙輔助判斷，當前位置前面的最近的人的位置，當前位置后面最近的人的位置，處于方便考慮位置0的可能，所以位置一律+1.

(2) 如果前面的位置沒人，所以左端的距離為i，如果后面的位置沒人，所以右端的位置為i+1。

(3) 如果左右都有人，則左右端計算即可，難度不高。文章來源地址http://www.zghlxwxcb.cn/news/detail-666807.html

到了這里，關(guān)于2023-08-22 LeetCode每日一題（到最近的人的最大距離）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！