可最多k次递减元素的最长全相等连续子数组长度最优解法问询

这题的最优解法是滑动窗口结合单调队列，时间复杂度O(n)，空间复杂度O(n)（单调队列的空间），这是能达到的最优时间复杂度了——毕竟你总得把数组遍历一遍对吧？

核心思路 #

首先得明确问题本质：我们只能对元素做递减操作，所以要让连续子数组的元素全部相等，最终的相等值一定是小于等于子数组里的所有元素的。总操作次数等于子数组的元素和减去「最终相等值 × 子数组长度」。要让总操作次数不超过k，等价于：
sum(subarray) - x * len(subarray) ≤ k，其中x ≤ min(subarray)

换个更直观的角度：把数组里的每个元素取反（比如B[i] = -A[i]），原问题的「递减操作」就变成了对B的「递增操作」，目标转化为找最长的连续子数组，使得对B的递增操作总次数不超过k——这就变成了一道经典的滑动窗口问题！在转化后的问题里，总操作次数是max(B[left..right]) * len(subarray) - sum(B[left..right]) ≤ k，逻辑是把所有元素加到当前窗口的最大值，总次数等于最大值乘长度减去子数组和。

具体步骤 #

我们直接处理原数组也可以，核心是用滑动窗口维护合法区间，同时用单调队列快速获取窗口内的最小值：

1. 滑动窗口维护：用左指针left和右指针right表示当前窗口范围，初始都为0。
2. 单调队列维护最小值：维护一个递增的单调队列，队列里存储数组元素的索引，对应的元素值递增，队列头部就是当前窗口的最小值：
   • 右指针移动时，把队列尾部所有比当前元素大的索引移除（它们不可能成为后续窗口的最小值），再把当前索引加入队列。
   • 左指针需要移动时，如果队列头部的索引刚好是left，说明这个最小值要被移出窗口，把它从队列头部移除。
3. 合法性校验：每次右指针移动后，计算当前窗口的元素和减去「最小值 × 窗口长度」，如果值大于k，就不断移动左指针，直到操作次数≤k为止。
4. 更新最长长度：每次调整完窗口后，计算当前窗口长度，更新全局最长长度。

示例推演 #

拿题目里的例子A = [1,7,3,4,6,5]，k=6来说：

• 当窗口走到[3,4,6,5]时，队列头部对应元素是3（索引2），窗口和为18，操作次数是18 - 3×4=6，刚好等于k，符合条件，窗口长度为4。
• 尝试扩大窗口包含前面的7时，操作次数会远大于6，所以左指针需要移动，最终最长合法窗口就是4。

代码实现（Python） #

def longestEqualSubarray(A, k):
    from collections import deque
    n = len(A)
    left = 0
    max_len = 0
    sum_sub = 0
    min_queue = deque()  # 递增队列，存储元素索引
    
    for right in range(n):
        sum_sub += A[right]
        # 维护单调队列，保证队列内元素对应的值递增
        while min_queue and A[right] <= A[min_queue[-1]]:
            min_queue.pop()
        min_queue.append(right)
        
        # 如果当前窗口操作次数超过k，移动左指针缩小窗口
        while sum_sub - A[min_queue[0]] * (right - left + 1) > k:
            sum_sub -= A[left]
            if min_queue[0] == left:
                min_queue.popleft()
            left += 1
        
        # 更新最长合法子数组长度
        max_len = max(max_len, right - left + 1)
    
    return max_len

# 测试示例
print(longestEqualSubarray([1,7,3,4,6,5], 6))  # 输出4

为什么这是最优解？ #

• 滑动窗口保证每个元素最多被左、右指针各访问一次，单调队列保证每个元素最多入队和出队一次，整体时间复杂度O(n)，这是线性时间，已经是最优的——你不可能比遍历一次数组更快。
• 空间复杂度主要来自单调队列，最坏情况下（数组严格递增）队列会存储所有元素，空间为O(n)，属于高效的空间占用。

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