You need to enable JavaScript to run this app. 求解固定长度子数组最小值的最大值 超时代码优化
优惠活动
大模型
产品
解决方案
定价
更多

求解固定长度子数组最小值的最大值 超时代码优化

原代码存在的核心问题
  • 时间复杂度过高:采用双层嵌套循环实现,外层遍历所有滑动窗口起点,内层逐个遍历窗口内的x个元素计算最小值,整体时间复杂度为O(n*x)。当数组长度较大、窗口尺寸偏长时,运算量会显著上升,直接触发运行超时。
  • 存在代码笔误:内层找最小值的循环里写的是Math.min(min, num.get(j)),这里的min是未定义的变量,实际应该用预先定义的minVal,这段代码本身无法通过编译,就算修正笔误,算法效率也不达标。
  • 冗余计算严重:每个窗口都从头开始遍历元素计算最小值,完全没有复用上一个窗口的比较结果,做了大量重复的无效运算。
高效实现的修正思路

这个题目是经典的滑动窗口类问题,核心目标是用*O(n)*的时间复杂度算出所有窗口的最小值,再从中取最大值即可,不需要对每个窗口单独遍历找最小值。
标准实现基于双端队列做单调维护,核心逻辑是:

  • 队列中存储数组元素的索引,保证队列内索引对应的元素值是单调递增的,队头永远是当前窗口的最小值对应的索引。
  • 遍历每个位置的元素时,同步完成3个维护动作:
    1. 从队尾弹出所有值大于等于当前元素的索引:这些元素在当前元素进入窗口后,永远不会成为后续窗口的最小值,可直接淘汰
    2. 弹出队头已经滑出当前窗口左边界的索引:这些元素已经不在当前窗口范围内,不能再参与最小值计算
    3. 当凑够第一个完整窗口后,取队头对应的元素作为当前窗口的最小值,同步更新所有窗口最小值的全局最大值
修正后的可运行代码
import java.util.*;

public static int max(int x, List<Integer> num) {
    int n = num.size();
    // 边界参数校验
    if (n == 0 || x <= 0 || x > n) {
        throw new IllegalArgumentException("输入参数不合法");
    }
    Deque<Integer> deque = new ArrayDeque<>();
    int maxOfMins = Integer.MIN_VALUE;

    for (int i = 0; i < n; i++) {
        // 维护队列单调递增:弹出队尾大于等于当前值的元素
        while (!deque.isEmpty() && num.get(deque.peekLast()) >= num.get(i)) {
            deque.pollLast();
        }
        deque.offer(i);

        // 弹出滑出窗口左边界的队头元素
        while (deque.peekFirst() <= i - x) {
            deque.pollFirst();
        }

        // 窗口形成后,计算当前窗口最小值并更新全局最大值
        if (i >= x - 1) {
            int currentMin = num.get(deque.peekFirst());
            maxOfMins = Math.max(maxOfMins, currentMin);
        }
    }
    return maxOfMins;
}

这个实现中每个元素最多入队、出队各一次,整体时间复杂度为O(n),完全可以满足大测试用例的运行时效要求,不会触发超时。


内容的提问来源于stack exchange,提问作者ppb

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.10.29 20:36:10