印刷行业网站建设,青岛外包加工网,mysql网站后台管理系统下载,2017做网站赚钱leetcode原题链接
题目描述#xff1a; 给你一个整数数组 nums#xff0c;有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。 返回 滑动窗口中的最大值 。 示例1: 输入#xff1a;nums [1,…leetcode原题链接
题目描述 给你一个整数数组 nums有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。 返回 滑动窗口中的最大值 。 示例1: 输入nums [1,3,-1,-3,5,3,6,7], k 3
输出[3,3,5,5,6,7]
解释
滑动窗口的位置 最大值
--------------- -----
[1 3 -1] -3 5 3 6 7 31 [3 -1 -3] 5 3 6 7 31 3 [-1 -3 5] 3 6 7 51 3 -1 [-3 5 3] 6 7 51 3 -1 -3 [5 3 6] 7 61 3 -1 -3 5 [3 6 7] 7示例2 输入nums [1,3,0,2,4]
输出0
解释
nums 无论怎么变化总是有 3 分。
所以我们将选择最小的 k即 0。提示 1 nums.length 105-104 nums[i] 1041 k nums.length 解题思路
方法一单调队列
单调队列队列中的元素是单调递增或单调递减的队列就是单调队列。 维护队列中的元素递增
对于这道题需要维护一个单调递增的队列。
由队尾到队头 元素是单调递增的。如果要入队元素大于队尾元素则队尾元素出队这是个循环操作如下
while(deque.peekLast() newElement){deque.pollLast();
}
deque.push(newElement); // 新元素入队如何保证队列中的元素是窗口内的因为窗口一直在向右移动 初始时窗口为1队列中元素为9, 8, 7。窗口向右移动时(窗口2)发现9已不是窗口中的元素但9依然在队列中且9为队列的队头元素需要将9从队列的队头弹出。所以需要进行如下判断:
if(deque.peekFirst() v){ // v为上一个窗口最左边的值。deque.poolFirst();
}整体代码如下
public int[] maxSlidingWindow(int[] nums, int k) {int n nums.length;int[] ans new int[n - k 1];DequeInteger deque new LinkedList();int idx 0;for(int i 0; i nums.length; i){// 保证队列中的元素是窗口内的if(!deque.isEmpty() i - k 0 nums[i - k] deque.peekFirst()){deque.pollFirst();}// 维护队列中的元素是递增的while (!deque.isEmpty() nums[i] deque.peekLast()){deque.pollLast();}deque.addLast(nums[i]);if(i k - 1){ans[idx] deque.peekFirst();}}return ans;
}方法二线段树
百度百科线段树 线段树中的每个节点存储的是这个区间的最大值。
整体代码如下
public int[] maxSlidingWindow(int[] nums, int k) {int len nums.length;int[] ans new int[len - k 1];this.tr new Node[len * 41];build(1,1,len);for(int i 0; ilen;i){update(1,i1,nums[i]);}for(int i 0; i len -k1;i){ans[i] query(1,i1,ik);}return ans;
}class Node {int l, r, v;Node(int l, int r) {this.l l;this.r r;v Integer.MIN_VALUE;}
}Node[] tr;void pushup(int u) {tr[u].v Math.max(tr[u 1].v, tr[u 1 | 1].v);
}void build(int u, int l, int r) {tr[u] new Node(l, r);if (l ! r) {int mid tr[u].ltr[u].r 1;build(u 1, l, mid);build(u 1 | 1, mid 1, r);}
}void update(int u, int x, int v){if(x tr[u].ltr[u].rx){tr[u].v Math.max(tr[u].v, v);} else{int mid tr[u].ltr[u].r1;if(xmid){update(u1,x,v);} else{update(u1|1,x,v);}pushup(u);}
}
int query(int u, int l, int r){if(l tr[u].ltr[u].rr){return tr[u].v;} else{int mid tr[u].ltr[u].r1;int ans Integer.MIN_VALUE;if(lmid){ans query(u1,l,r);} if(rmid){ans Math.max(query(u1|1,l,r),ans);}return ans;}
}
