849. Maximize Distance to Closest Person ——weekly contest 87
阅读原文时间:2023年07月09日阅读:1

题目链接:https://leetcode.com/problems/maximize-distance-to-closest-person/description/

思路:pre[i]存放i之前离最近的1的距离。post记录之后的。 res = max(min(pre[i],[post[i]))

注意点:初始nst需要设计极大或极小值。

1 int maxDistToClosest(vector& seats) {
2 vector pre,post;
3 int n = seats.size();
4 pre.assign(n,0);
5 post.assign(n,0);
6 int nst = -200000;
7 for(int i = 0; i < n; i++){ 8 if(seats[i] == 1){ 9 nst = i; 10 }else{ 11 pre[i] = i - nst; 12 } 13 } 14 nst = 200000; 15 for(int i = n - 1; i >= 0; i--){
16 if(seats[i]==1){
17 nst = i;
18 }else{
19 post[i] = nst - i;
20 }
21 }
22 int res = 0;
23 for(int i = 0; i<n; i++ ){
24 int temp = min(pre[i],post[i]);
25 res = max(res,temp);
26 }
27 return res;
28 }