带2座间隔的影院座位安排：求最大可容纳人数

问题描述 #

给定数组 [0,0,0,1,0,0,1,0,0,0]，其中1代表已占用座位，0代表未占用座位。需要计算在满足人与人之间间隔至少2个座位的规则下，该座位数组可容纳的最大人数。

你的代码问题分析 #

你尝试用滑动窗口思路，但当前代码逻辑存在明显问题：

• 滑动窗口的条件判断完全不符合座位间隔规则：array[p1] !== array[p2]的判断逻辑和“间隔2个座位”的要求毫无关联，无法正确识别可坐位置
• 窗口边界与移动逻辑错误：p1, p2 <= array.length是无效的JS语法，实际仅会判断p2 <= array.length；且固定窗口大小为3的设计也不适用于所有场景

正确的解决方案 #

我们可以通过遍历每个座位，逐一检查当前位置是否满足“自身未被占用、前后各两个座位也未被占用”的条件，满足则标记为已占用并计数。具体逻辑如下：

1. 复制原数组避免修改原始数据
2. 遍历每个座位索引i：
   • 先确认当前座位seats[i]为0（未被占用）
   • 检查左侧相邻的1-2个座位（如果存在）是否都为0
   • 检查右侧相邻的1-2个座位（如果存在）是否都为0
   • 所有条件满足则标记该座位为1，计数加1

代码实现 #

function maxCinSeating(array) {
  const seats = [...array];
  let count = 0;
  const len = seats.length;

  for (let i = 0; i < len; i++) {
    if (seats[i] === 0) {
      // 检查左侧两个座位是否都未被占用（边界情况特殊处理）
      const leftValid = (i === 0 || seats[i-1] === 0) && (i < 2 || seats[i-2] === 0);
      // 检查右侧两个座位是否都未被占用（边界情况特殊处理）
      const rightValid = (i === len-1 || seats[i+1] === 0) && (i > len-3 || seats[i+2] === 0);
      
      if (leftValid && rightValid) {
        seats[i] = 1;
        count++;
      }
    }
  }
  return count;
}

// 测试示例
console.log(maxCinSeating([0, 0, 0, 1, 0, 0, 1, 0, 0, 0])); // 输出：2

结果说明 #

对于示例数组[0,0,0,1,0,0,1,0,0,0]，最大可容纳2人：

• 可选位置组合一：索引0（前后无冲突）和索引8（与右侧已占座位间隔2个位置）
• 可选位置组合二：索引2（与右侧已占座位间隔1个位置？不，索引2右侧是索引3的1，间隔1个位置？哦不对，索引2和3之间是相邻，所以不能选索引2，应该是索引0和8，或者索引0和9？不对，索引9右侧无座位，左侧是索引7、8都是0，所以索引9可以坐，此时索引0和9，间隔9个位置，满足条件；或者索引8和0，都是可以的，总之最大计数是2。

内容的提问来源于stack exchange，提问作者Mohit