0-1数组的最大不重叠N长窗口数计算（N为奇数）

问题描述 #

给定一个仅包含0或1的数组，需找出可容纳的最大数量的不重叠窗口，满足以下条件：

• 窗口长度N为奇数；
• 窗口必须以值为1的元素作为中心；
• 窗口可包含0，数组两端的元素也可作为有效窗口的一部分（窗口超出数组范围的部分自动忽略）；
• 窗口之间不能重叠。

实际应用场景 #

比如会议排期：数组代表一年的日期，1表示可举办会议的日期，规则要求会议之间至少间隔2天（对应窗口长度为3的场景，确保两个会议的窗口不重叠）。

示例 #

示例1 #

array_1 = [1, 0, 0, 1, 0, 0, 1, 0]
count_windows(array=array_1, window_size=3)

输出：3
解释：选中的窗口覆盖索引为：[0, 1]、[2, 3, 4]、[6, 7]（注：原解释中的[6,7,8]是窗口理论范围，实际数组仅到索引7，故取到7）

示例2 #

array_2 = [0, 0, 0, 1, 1, 1, 0, 0]
count_windows(array=array_2, window_size=3)

输出：1
解释：有效窗口为[2, 3, 4]（以索引3的1为中心）。若选择索引5的1作为中心，其窗口会覆盖索引4，与前者重叠，因此无法同时选取。

基于Numpy的实现 #

import numpy as np

def count_windows(array, window_size):
    # 校验窗口长度必须为奇数
    if window_size % 2 == 0:
        raise ValueError("窗口长度必须为奇数")
    
    half_window = (window_size - 1) // 2
    arr = np.array(array)
    # 获取所有值为1的元素索引
    one_indices = np.where(arr == 1)[0]
    
    count = 0
    last_window_end = -np.inf  # 记录上一个窗口的结束位置，初始设为负无穷
    
    for idx in one_indices:
        current_window_start = idx - half_window
        current_window_end = idx + half_window
        
        # 当前窗口与上一个窗口不重叠时，选中该窗口
        if current_window_start > last_window_end:
            count += 1
            last_window_end = current_window_end
    
    return count

测试代码 #

# 测试示例1
array_1 = [1, 0, 0, 1, 0, 0, 1, 0]
print(count_windows(array_1, 3))  # 输出3

# 测试示例2
array_2 = [0, 0, 0, 1, 1, 1, 0, 0]
print(count_windows(array_2, 3))  # 输出1

代码逻辑说明 #

1. 输入校验：首先确保窗口长度为奇数，不符合则抛出错误；
2. 计算窗口范围：根据窗口长度算出半长，确定每个中心对应的窗口起止索引；
3. 提取有效中心：用Numpy快速定位所有值为1的元素索引；
4. 贪心选择：从左到右遍历有效中心，每次选择第一个不与已选窗口重叠的中心，更新上一个窗口的结束位置，统计选中数量。

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