Leetcode 849. Maximize Distance

文章作者：Tyan
博客：noahsnail.com  |  CSDN  |  简书

1. Description

Maximize Distance to Closest Person

2. Solution

• Version 1

class Solution {
public:
    int maxDistToClosest(vector<int>& seats) {
        int max_distance = 0;
        int distance = 0;
        int left = -1;
        int right = -1;
        int size = seats.size();
        for(int i = 0; i < seats.size(); i++) {
            if(!seats[i]) {
                getRight(seats, right, i);
                calculateDistance(i, left, right, max_distance, size);
            }
            else {
                left = i;
            }
        }
        return max_distance;
    }

private:
    void calculateDistance(int current, int left, int& right, int& max_distance, int size) {
        int distance_left = INT_MAX;
        int distance_right = INT_MAX;
        int distance = 0;
        if(left > -1) {
            distance_left = current - left;
        }
        if(right < size){
            distance_right = right - current;
        }
        distance = min(distance_left, distance_right);
        max_distance = max(max_distance, distance);
    }
    
    void getRight(vector<int>& seats, int& right, int current) {
        if(right <= current) {
            for(int i = current + 1; i < seats.size(); i++) {
                if(seats[i]) {
                    right = i;
                    break;
                }
                else {
                    right = i + 1;
                }
            }
        }
    }
};

• Version 2

class Solution {
public:
    int maxDistToClosest(vector<int>& seats) {
        int max_distance = 0;
        int distance = 0;
        int left = -1;
        int right = seats.size() - 1;
        for(int i = 0; i < seats.size(); i++) {
            if(seats[i]) {
                if(left == -1) {
                    max_distance = max(max_distance, i);
                }
                else {
                    max_distance = max(max_distance, (i - left) / 2);
                }
                left = i;
            }
        }
        if(!seats[right]) {
            max_distance = max(max_distance, right - left);
        }
        return max_distance;
    }
};

Reference

1. https://leetcode.com/problems/maximize-distance-to-closest-person/description/