esc to dismiss
x
Home / week-88 / 879

信息

题解

解法1

记录到最近有人的距离
  1. 从左, 从右各扫描一次, 记录当前位置到 "前" 一个有人的位置的距离, 最后取 左右 距离中的最小值, 即为这个位置到最近人的距离
  2. 两端的特殊处理
  3. 从左到右, 如果第一个位置为0, 则其相对左边的距离, 应为无限大
  4. 可以记为n, 这样取最小值时可以用右边的距离值,
  5. 同理从右到左
  6. 如果位置已经被占用, 则使用 -1 标识 
pub fn max_dist_to_closest(seats: Vec<i32>) -> i32 {
    let n = seats.len() as i32;

    let (mut left, mut right) = (vec![-1; seats.len()], vec![-1; seats.len()]);
    let (mut from_left, mut from_right) = (-n, n + n - 1);

    for i in 0..seats.len() {
        if seats[i] == 1 {
            // 已经被占住了
            left[i] = -1;
            from_left = i as i32; // 更新左边的人的位置
        } else {
            left[i] = (i as i32) - from_left;
        }
    }
    for i in (0..seats.len()).rev() {
        if seats[i] == 1 {
            right[i] = -1;
            from_right = i as i32;
        } else {
            right[i] = from_right - (i as i32);
        }
    }

    left.into_iter()
        .zip(right.into_iter())
        .map(|(a, b)| a.min(b))
        .max()
        .unwrap_or(0)
}

解法2

按 0 分段
  1. 由于距离是向左向右两侧的, 取其中的最小值, 因此在成段的0, 只有中间那个位置才可能是想要的位置
  2. 中间位置到两端的距离, 在段长是奇数还是偶数时略有不同
  3. 两端的特殊处理
  4. 如果只在一端找到了1, 则只有开头/结尾可能是想要的位置 
pub fn max_dist_to_closest(seats: Vec<i32>) -> i32 {
    let n = seats.len() as i32;
    let (mut prev, mut future) = (-n, 0);
    let mut ans = 0;

    let mut cursor = 0;
    while cursor < seats.len() {
        if seats[cursor] == 1 {
            prev = cursor as i32;
            cursor += 1;
            continue;
        }
        future = cursor;
        while future < seats.len() && seats[future] == 0 {
            future += 1;
        }
        let length = (future - cursor) as i32;
        if prev < 0 {
            // 开头, 只有右端找到了1
            ans = ans.max(length);
        } else if future == seats.len() {
            // 结尾, 只有左端有1
            ans = ans.max(length);
        } else {
            if length % 2 == 0 {
                ans = ans.max(length / 2);
            } else {
                ans = ans.max(length / 2 + 1);
            }
        }
        cursor = future; // 成段的0, 只需要判断一次
    }
    ans
}

Backlinks

Tags

x