Ruby高效数组操作：解决滑动窗口最小值最大值计算超时问题

业务需求 #

输入固定长度参数x和整数数组space，最终需要返回的结果是：所有长度为x的连续滑动区间的最小值中的最大值。
举个实际计算的例子：

space = [1, 2, 3, 1, 2]
x = 2
# 拆分出的滑动区间依次为
# [1, 2] [2, 3] [3, 1] [1, 2]
# 每个区间对应的最小值依次为
# [1, 2, 1, 1]
# 取这些最小值的最大值，最终返回结果为2

现有实现的问题 #

当前代码在多数小数据量测试用例下可以正常运行，但大数组场景下会因为执行时间超限失败。现有代码如下：

def segment(x, space)
    minimums = {}
    space.each_with_index do |_val, index|
        # 生成当前滑动区间
        mark = x - 1
        break if mark >= space.length 
        segment = space[index..mark]
        x = x + 1    
        # 计算当前区间的最小值
        minimum = segment.min
        minimums[index] = minimum
    end
    
    # 取所有区间最小值的最大值作为返回
    return minimums.values.max
end

之前尝试过的调整方向：

• 把存储最小值的minimums结构从哈希改为数组，没有带来明显的性能提升
• 考虑过将space数组转换为哈希后操作，评估下来逻辑复杂度更高，没有可行收益

性能瓶颈分析 #

现有实现的时间复杂度为O(nx)*，核心开销来自两部分：

1. 每移动一次滑动窗口，都要切片生成一个长度为x的新数组，产生不必要的内存拷贝开销；且代码靠循环内自增x来对齐切片终点的写法非常冗余，没有简化逻辑。
2. 对每个切片单独调用min方法，需要完整遍历整个切片元素，累计遍历的元素总量为*(n -x +1)* x，在n和x数值较大时，总遍历量会快速膨胀，导致超时。

优化方案 #

将计算滑动窗口最小值的逻辑改用单调双端队列实现，可以把整体时间复杂度降到O(n)，完全满足大数据量下的性能要求。
核心实现逻辑：

• 维护一个双端队列，队列中存储数组元素的下标，始终保证队列对应的元素值是单调递增的——队首永远是当前窗口内的最小值下标
• 每滑动一次窗口，按顺序完成三步操作：
  • 弹出队首中超出当前窗口范围的过期下标
  • 从队尾开始，弹出所有比新进入窗口的元素值大的下标，保证队列的单调性
  • 把新元素的下标插入队尾
• 当窗口长度达到要求的x时，队首对应的元素就是当前窗口的最小值，记录后同步更新“所有最小值中的最大值”即可。每个元素最多入队、出队一次，没有重复遍历的开销。

优化后的Ruby实现 #

def segment(x, space)
  return nil if space.length < x
  deque = []
  max_of_mins = -Float::INFINITY

  space.each_with_index do |val, i|
    # 移除队首超出窗口范围的元素
    deque.shift while !deque.empty? && deque[0] <= i - x
    # 维护队列的单调递增性质
    deque.pop while !deque.empty? && space[deque.last] >= val
    deque << i
    # 窗口成型后，计算当前窗口最小值并更新最终结果
    if i >= x - 1
      current_min = space[deque.first]
      max_of_mins = current_min if current_min > max_of_mins
    end
  end

  max_of_mins
end

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