面试算法题：布尔数组中翻转k个false为true以最大化连续true长度

这个问题其实是滑动窗口算法的经典应用场景，比暴力解法高效太多了，我来给你详细拆解一下思路和实现方式：

核心思路：滑动窗口（Sliding Window） #

我们可以用两个指针（左指针left、右指针right）维护一个有效窗口——窗口内最多包含k个False（因为我们最多能翻转k个）。通过动态调整窗口的边界，找到满足条件的最大窗口，这个窗口就是翻转后最长的连续True片段，窗口内的False就是需要被翻转的目标。

具体步骤如下：

• 初始化左指针left=0，统计窗口内False数量的计数器falseCount=0，同时记录窗口内False位置的列表falsePositions
• 右指针right从数组开头向右遍历：
  • 遇到False时，falseCount加1，同时把当前位置加入falsePositions
  • 当falseCount超过k时，移动左指针left向右，直到窗口内的False数量≤k（如果左指针指向的是False，要同步减少falseCount并移除falsePositions的第一个元素）
  • 每次调整窗口后，计算当前窗口的长度，如果比之前记录的最大长度更长，就更新最大长度和最佳窗口的左右边界

结合示例的具体推演 #

拿你给出的示例数组：[T,F,T,T,F,F,F,T,F,F,F,F,T]，k=3来举例：

1. 右指针移动到索引6时，窗口内的False数量达到4（索引1、4、5、6），超过k=3，此时需要移动左指针到索引2（跳过索引1的False），窗口内False数量回到3（索引4、5、6）
2. 继续移动右指针到索引7（元素是T），此时窗口是[T,T,F,F,F,T]（索引2到7），长度为6，这是当前最大的有效窗口
3. 这个窗口内的False位置是[4,5,6]，把这三个位置的F翻转成T，就得到了你给出的解决方案：T F T T T* T* T* T F F F F T

伪代码实现 #

def find_longest_true_with_k_flips(arr, k):
    left = 0
    max_length = 0
    best_left = 0
    best_right = 0
    false_count = 0
    false_positions = []
    
    for right in range(len(arr)):
        if not arr[right]:  # 假设arr中用False表示F，True表示T
            false_count += 1
            false_positions.append(right)
        
        # 当窗口内False数量超过k时，收缩左边界
        while false_count > k:
            if not arr[left]:
                false_count -= 1
                false_positions.pop(0)
            left += 1
        
        # 更新最大窗口信息
        current_length = right - left + 1
        if current_length > max_length:
            max_length = current_length
            best_left = left
            best_right = right
    
    # 返回最长长度、需要翻转的位置、最佳窗口的边界
    return {
        "max_length": max_length,
        "flip_positions": false_positions,
        "window_start": best_left,
        "window_end": best_right
    }

关键注意事项 #

• 时间复杂度：O(n)，因为每个元素最多被左右指针各访问一次，相比暴力法的O(n²)效率提升非常明显
• 边界情况处理：如果数组中False的总数≤k，那么直接翻转所有False，整个数组就是最长的连续True片段
• 精准定位翻转位置：通过falsePositions列表，我们可以准确知道哪些位置需要翻转，而不仅仅是得到最长片段的长度

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