最长全相同元素连续子数组长度问题：基于k次递减的最优解法问询

嘿，这题的最优解法绝对是滑动窗口（双指针），时间复杂度O(n)，空间复杂度最多O(n)，比暴力枚举所有子数组的O(n²)解法高效太多了！我给你把思路和实现拆解清楚：

我们的目标是找到最长的连续子数组，通过最多k次递减操作让所有元素相同。这里有个关键观察：把所有元素减到子数组中的最大值是最省操作次数的（因为只能递减，选最大的目标值不需要额外增加操作，反而如果选更小的值，操作次数只会更多）。

滑动窗口的核心就是维护一个满足「操作次数≤k」的窗口，不断扩大右边界，当操作次数超过k时，移动左边界缩小窗口，全程记录窗口的最大长度。

1. 维护窗口边界：用left和right两个指针分别表示窗口的左右边界，初始都为0。
2. 快速计算操作次数：操作次数 = 窗口内最大值 × 窗口长度 - 窗口内元素总和。这里可以用前缀和数组快速计算窗口总和，避免每次遍历求和。
3. 高效维护窗口最大值：用单调队列来维护窗口内最大值的索引，队首始终是当前窗口最大值的位置，保证O(1)时间获取最大值，避免每次遍历找最大值的O(n)开销。
4. 窗口调整逻辑：
   • 不断移动右指针扩大窗口，更新前缀和和单调队列。
   • 计算当前窗口的操作次数，如果超过k，就移动左指针缩小窗口，同时更新单调队列（如果左指针指向的是当前最大值的索引，要从队首弹出）。
   • 每次调整后，更新记录的最大窗口长度。

输入数组[1,7,3,4,6,5]，k=6：
当窗口为[3,4,6,5]时，最大值是6，窗口长度4，总和是3+4+6+5=18，操作次数=6×4-18=6，刚好等于k，满足条件，所以窗口长度4就是答案。

def longestEqualSubarray(A, k):
    from collections import deque
    max_len = 0
    left = 0
    # 前缀和数组，prefix_sum[i]表示前i个元素的和（A[0]到A[i-1]）
    prefix_sum = [0] * (len(A) + 1)
    # 单调队列：存储窗口内元素的索引，队首对应元素是窗口最大值
    max_deque = deque()
    
    for right in range(len(A)):
        # 更新前缀和
        prefix_sum[right + 1] = prefix_sum[right] + A[right]
        # 维护单调队列：弹出队尾所有比当前元素小的索引，保证队列单调递减
        while max_deque and A[right] >= A[max_deque[-1]]:
            max_deque.pop()
        max_deque.append(right)
        
        # 计算当前窗口需要的操作次数
        window_size = right - left + 1
        current_max = A[max_deque[0]]
        operations = current_max * window_size - (prefix_sum[right + 1] - prefix_sum[left])
        
        # 如果操作次数超过k，移动左指针缩小窗口
        while operations > k:
            # 如果左指针是当前最大值的索引，从队首移除
            if max_deque[0] == left:
                max_deque.popleft()
            left += 1
            window_size = right - left + 1
            current_max = A[max_deque[0]] if max_deque else 0
            operations = current_max * window_size - (prefix_sum[right + 1] - prefix_sum[left])
        
        # 更新最长子数组长度
        max_len = max(max_len, window_size)
    
    return max_len

• 时间复杂度：O(n)，每个元素最多入队和出队单调队列各一次，左右指针总共移动n次。
• 空间复杂度：O(n)，前缀和数组和单调队列的最坏情况（数组单调递减）会存储n个元素。

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