当前位置：首页 > news >正文

Leetcode——239. 滑动窗口最大值

news 来源：原创 2025/9/5 20:52:54

题解一

思路

第一次做困难的题，确实把我既困住了又难住了，确实自己一点都想不出来。

这个思路，差不多就是，自己定义一个单调队列。

添加的时候，判断是否比队列最后的元素大，如果比它大，就把末尾的元素弹出，保证队列里从队头到队尾是单调递减的，这样的话，peek()方法调出的元素，就永远是滑动窗口里最大的元素；删除元素的时候，因为有些元素有可能在还没删除的时候就已经被删掉了，所以说要判断被删的元素是不是在单调队列里（这也是我后面暴力解的时候，没解决的问题），如果在队列里就把他删掉，由队列里第二大的元素变成队头。peek()方法调用的依旧是滑动窗口里最大的元素。

代码

class Solution {public int[] maxSlidingWindow(int[] nums, int k) {if(k == 1){return nums;}int length = nums.length;MyQueue myQueue = new MyQueue();int[] maxNums = new int [length - k + 1];for(int i = 0; i < k; i++){myQueue.offer(nums[i]);}maxNums[0] = myQueue.peek();int index = 1;for(int i = k; i < length; i++){myQueue.offer(nums[i]);myQueue.poll(nums[i - k]);maxNums[index++] = myQueue.peek();}return maxNums;}
}
class MyQueue{Deque<Integer> queue = new ArrayDeque<>();public void offer(int val){while(!queue.isEmpty() && val > queue.getLast()){queue.removeLast();}queue.offer(val);}public void poll(int val){if(!queue.isEmpty() && val == queue.peek()){queue.poll();}}public int peek(){return queue.peek();}
}

总结

不愧是困难的题，确实想不出来。但是掌握单调队列这个解题思路，以及getLast()方法，还有removeLast()方法。

题解二

思路

暴力解思路就很简单了，每次有元素的替换的时候就遍历下数组里的元素，看看哪个最大

ps：但是这道题是困难，因此有几个用例会超时，所以并不算严格意义上的题解。

代码

class Solution {public int[] maxSlidingWindow(int[] nums, int k) {int length = nums.length;if(k == 1){return nums;}if(k == length){int max = 0;for(int i : nums){if(i > max){max = i;}}return new int[]{max};}int maxNums[] = new int [length - k + 1];int max = 0;int left = 0;int right = 0;int index = 0;while(right < length){if(right - left < k - 1){right++;}else if(right - left == k - 1){int max2 = nums[left];for(int i = left; i <= right; i++){if(nums[i] > max2){max2 = nums[i];}}maxNums[index++] = max2;left++;}}return maxNums;}
}

题解一

思路

代码

总结

题解二

思路

代码

相关文章：