思路及解答暴力法

📅 2026/7/1 6:45:35 👁️ 次浏览

遍历每个可能的窗口起始位置计算窗口内的最大值javapublic class Solution { public int[] maxSlidingWindow(int[] nums, int k) { // 处理边界情况 if (nums null || nums.length 0 || k 0 || k nums.length) { return new int[0]; } int n nums.length; int[] result new int[n - k 1]; // 结果数组 // 遍历每个窗口的起始位置 for (int i 0; i n - k; i) { int max Integer.MIN_VALUE; // 计算当前窗口内的最大值 for (int j i; j i k; j) { if (nums[j] max) { max nums[j]; } } result[i] max; } return result; } }时间复杂度O(n×k)需要处理n-k1个窗口每个窗口需要k次比较空间复杂度O(1)除结果数组外只使用常数空间双端队列法最优解⾸先进⾏⾮空判断以及数组⻓度是否不为 0 是否不⼩于窗⼝⻓度。其次使⽤⼀个双向链表⾥⾯保存的是索引遍历每⼀个元素如果双向队列不为空且最后的元素作为索引的数值⼩于当前的元素就把当前的元素的索引加到队列的后⾯。这样可以保证队列从头到尾是单调递减的也就是队尾的元素就是最⼩的元素。然后把当前的元素加进去队列尾部。判断队列前⾯的元素是不是索引位置不符合如果不符合就移除队列头部的元素。那么此时的队列⾸部肯定就是滑动窗⼝的最⼤值。此处应该判断滑动窗⼝⽣效的索引以 2, 3, 4, 2, 6, 2, 5, 1 为例所有的窗⼝最⼤值⾄此已经收集完成。javapublic class Solution64 { public static void main(String[] args) { int[] nums {2, 3, 4, 2, 6, 2, 5, 1}; System.out.println(new Solution64().maxInWindows(nums, 3)); } public ArrayListInteger maxInWindows(int[] num, int size) { ArrayListInteger results new ArrayList(); if (num null || num.length 0 || num.length size || size 0) { return results; } LinkedListInteger integers new LinkedList(); for (int i 0; i num.length; i) { while (!integers.isEmpty() num[integers.peekLast()] num[i]) { integers.removeLast(); } integers.addLast(i); while (i - integers.peekFirst() size) { integers.removeFirst(); } if (i size - 1) { results.add(num[integers.peekFirst()]); } } return results; } }时间复杂度On,所有的元素都进⼊队列再出队列空间复杂度O(n)使⽤额外的队列空间存储索引以及窗⼝最⼤值。动态规划法分块思想将数组分成大小为k的块预处理每个位置的左右最大值分块思想将数组划分为大小为k的块最后一块可能不满left[i]从当前块开始到位置i的最大值right[i]从位置i到当前块结束的最大值窗口最大值计算对于窗口[i, ik-1]如果窗口完全在一个块内right[i]或left[ik-1]就是最大值如果窗口跨越两个块最大值 max(右块的左最大值, 左块的右最大值)javapublic class Solution { public int[] maxSlidingWindow(int[] nums, int k) { if (nums null || nums.length 0 || k 0) { return new int[0]; } int n nums.length; if (k 1) return nums; // 窗口大小为1直接返回原数组 int[] left new int[n]; // 从左到右的块最大值 int[] right new int[n]; // 从右到左的块最大值 int[] result new int[n - k 1];

相关新闻