西安网站开发方案,公司网站建设服务费怎么做账,自己做网站卖东西怎么样,wordpress上传到服务器题目链接
滑动窗口最大值
题目描述 注意点
只可以看到在滑动窗口内的 k 个数字返回 滑动窗口中的最大值1 k nums.length
解答思路
首先使用双端队列解决本题#xff0c;队列中存储的是元素在数组中的下标#xff0c;不断往队尾添加元素下标。在双端队列中 k nums.length
解答思路
首先使用双端队列解决本题队列中存储的是元素在数组中的下标不断往队尾添加元素下标。在双端队列中其保证该队列中存储的元素始终是某个滑动窗口所以在添加某个元素下标i时当队首的下标小于i - k 1该元素已经不属于该滑动窗口需要将队首的元素弹出。除此之外还要保证队首的元素为当前队列中的最大值所以在某个元素加入队列中时如果其值大于队尾的元素则要将队尾的元素都弹出直到队尾的值大于当前元素为止这样做保证元素在队列中始终从大到小排序同时这些元素在数组中下标都是从小到大。保证队首为任意滑动窗口的最大值的原理是队首元素始终是它所处的滑动窗口的最大值直到该元素已经不在滑动窗口或后方有一个更大值new_max中此时分为两种情况 1如果该元素已经不在滑动窗口则该元素会从队首中弹出其后方的元素会作为新的队首元素成为新滑动窗口的最大值 2如果其后方有一个更大值new_max此时会将所有的队列值都弹出因为滑动窗口始终往右滑动所以后续无论滑动多少new_max左侧的元素值都不可能比new_max更大new_max作为该块滑动窗口的最大值
代码
class Solution {public int[] maxSlidingWindow(int[] nums, int k) {int n nums.length;int[] res new int[n - k 1];DequeInteger deque new ArrayDeque(k);for (int i 0; i n; i) {// 窗口滑动if (!deque.isEmpty() deque.getFirst() i - k 1) {deque.removeFirst();}// 保证队列首部一定是该滑动窗口的最大值while (!deque.isEmpty() nums[deque.getLast()] nums[i]) {deque.removeLast();}deque.addLast(i);// 创建队列的过程中if (i k - 1) {continue;}// 滑到k - 1位置处开始计算滑动窗口最大值res[i - k 1] nums[deque.getFirst()];}return res;}
}关键点
双端队列的相关方法如何保证队首为滑动窗口的最大值什么时候应该对队尾的元素弹出
