求解固定长度子数组最小值的最大值 超时代码优化
原代码存在的核心问题
- 时间复杂度过高:采用双层嵌套循环实现,外层遍历所有滑动窗口起点,内层逐个遍历窗口内的x个元素计算最小值,整体时间复杂度为O(n*x)。当数组长度较大、窗口尺寸偏长时,运算量会显著上升,直接触发运行超时。
- 存在代码笔误:内层找最小值的循环里写的是
Math.min(min, num.get(j)),这里的min是未定义的变量,实际应该用预先定义的minVal,这段代码本身无法通过编译,就算修正笔误,算法效率也不达标。 - 冗余计算严重:每个窗口都从头开始遍历元素计算最小值,完全没有复用上一个窗口的比较结果,做了大量重复的无效运算。
高效实现的修正思路
这个题目是经典的滑动窗口类问题,核心目标是用*O(n)*的时间复杂度算出所有窗口的最小值,再从中取最大值即可,不需要对每个窗口单独遍历找最小值。
标准实现基于双端队列做单调维护,核心逻辑是:
- 队列中存储数组元素的索引,保证队列内索引对应的元素值是单调递增的,队头永远是当前窗口的最小值对应的索引。
- 遍历每个位置的元素时,同步完成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
相关产品推荐
相关产品推荐

