【原创】leetCodeOj --- Sliding Window Maximum 解题报告
天，这题我已经没有底气高呼“水”了。。。
题目的地址：
https://leetcode.com/problems/sliding-window-maximum/
题目内容：
Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.
For example,
Given nums = [1,3,-1,-3,5,3,6,7], and k = 3.
Window position Max
--------------- -----
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
Therefore, return the max sliding window as [3,3,5,5,6,7].
Note:
You may assume k is always valid, ie: 1 ≤ k ≤ input array's size for non-empty array.
Follow up:
Could you solve it in linear time?
题目解析：
关键是线性时间。开头我试图通过动态规划定义子问题来解决，然而这并没有什么卵用，怀疑自己已经患上了一定程度的动态规划病，需要重读CLRS回炉一番
其实有第二个关键点。均摊复杂度和严格复杂度，对于“线性时间内解决”这个要求而言，并没有什么不同的地方。
第三个关键点，就是这是一个动态维护的队列，你要在不重新遍历队中元素的情况下维护一个最值。
不知道各位是否做过O(1)时间内维护一个栈中最值的问题，如果没有，可以看看这篇老文：
【原创】leetCodeOj --- Min Stack 解题报告
那位说了，刚才还讲本质上是动态队列，现在你拿栈出来坑蒙拐骗，放学别走
别急别急，不是还能用栈模拟队列吗？
两个栈，队列的push操作，就把元素压到栈1。队列的pop操作，首先检查栈2是否非空，若栈2有元素，直接pop。若栈2无元素，则把当前栈1中全部的元素压进栈2。
这样，我们能够维护一个栈中的最值，就能维护一个队列中的最值。
因为当前队列中的全部元素都分布在这两个栈中，因此，这两个栈的最值再比一轮，就是最后的最值。
又有人问了，pop一次，栈2有东西还好，若没有，就得捣腾半天，把栈1的元素挨个压进栈2，这算哪门子线性时间？
还真是线性时间，别忘了均摊复杂度
每个元素，进队被压进一次栈1，出队时被压进栈2一次，算上弹出操作2次，一共只有4次操作。
一共n个元素
那就是4n个操作
不就是线性吗？
关键在于，一次实际的操作可能只有弹出一次，而压栈的操作被集成在某次弹出时集中执行了。
具体代码：
public class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
if (nums.length == 0) {
return nums;
}
int[] res = new int[nums.length - k + 1];
MinQueue queue = new MinQueue();
for (int i = 0; i < k; i ++) {
queue.push(nums[i]);
}
res[0] = queue.getMax();
int index = 1;
for (int i = k; i < nums.length; i ++) {
queue.pop();
queue.push(nums[i]);
res[index ++] = queue.getMax();
}
return res;
}
class MinQueue {
LinkedList<Integer> stack1 = new LinkedList<Integer>();
LinkedList<Integer> stack2 = new LinkedList<Integer>();
LinkedList<Integer> maxOne = new LinkedList<Integer>();
LinkedList<Integer> maxTwo = new LinkedList<Integer>();
public void push(Integer item) {
pushOne(item);
}
public Integer pop() {
Integer res = null;
if (stack2.size() == 0) {
while (stack1.size() != 0) {
pushTwo(popOne());
}
}
res = stack2.pop();
maxTwo.pop();
return res;
}
public Integer getMax() {
Integer one = maxOne.peek();
Integer two = maxTwo.peek();
if (one == null) {
return two;
} else if (two == null){
return one;
}
return one > two ? one : two;
}
private Integer popOne() {
Integer res = null;
maxOne.pop();
res = stack1.pop();
return res;
}
private void pushOne(Integer item) {
stack1.push(item);
if (stack1.size() == 1) {
maxOne.push(item);
} else {
Integer front = maxOne.peek();
if (front < item) {
maxOne.push(item);
} else {
maxOne.push(front);
}
}
}
private void pushTwo(Integer item) {
stack2.push(item);
if (stack2.size() == 1) {
maxTwo.push(item);
} else {
Integer front = maxTwo.peek();
if (front < item) {
maxTwo.push(item);
} else {
maxTwo.push(front);
}
}
}
}
}
最新文章
- 编译器开发系列--Ocelot语言4.类型定义的检查
- 传统软件和SaaS，差异究竟在哪里
- [转]opencv3.0 鱼眼相机标定
- Recovering deleted Records
- epon e8-c HG220GS超级密码破解
- memcache相同主域名下的session共享
- topcoder SRM 625 DIV2 IncrementingSequence
- 20145320《Java程序设计》第二次实验报告
- JMeter学习（十）内存溢出解决方法
- iOS之多控制器管理--项目中的常见文件
- 利用MutationObserver对页面元素的改变进行监听
- PHP各版本之间差异
- QUdpSocket Class
- js中的 substring和substr方法
- Linux磁盘故障案例
- Dubbo 的配置主要分为三大类
- transitionEnd不起作用解决方法
- 如何使用HttpClient包实现JAVA发起HTTP请求？
- Spring Security 使用数据库用户进行认证
- openvas漏洞扫描