题解 | #滑动窗口的最大值# | JAVA | 自己写单调队列实现
滑动窗口的最大值
http://www.nowcoder.com/practice/1624bc35a45c42c0bc17d17fa0cba788
运行时间:13ms
超过77.89% 用Java提交的代码
占用内存:9656KB
超过14.87%用Java提交的代码
编写一个单调队列
这个队列要有如下功能:
具有MAX函数, 获取当前队列最大值
获取o(1)
public class SingleQueue { LinkedList<Integer> q = new LinkedList<>(); public void push(int n) { // 将小于 n 的元素全部删除 while (!q.isEmpty() && q.getLast() < n) { q.pollLast(); } // 然后将 n 加入尾部 q.addLast(n); } public int max() { return q.getFirst(); } public void pop(int n) { if (n == q.getFirst()) { q.pollFirst(); } } }
进行代码编写
import java.util.*; public class Solution { public ArrayList<Integer> maxInWindows(int [] nums, int k) { ArrayList<Integer> result = new ArrayList<>(); if(nums.length == 0){return result;} SingleQueue window = new SingleQueue(); for (int i = 0; i < nums.length && k > 0 ; i++) { //少进一个人 if (i < k - 1) { window.push(nums[i]); } else { //进入 window.push(nums[i]); //找到最大的 result.add(window.max()); //出去 window.pop(nums[i - k + 1]); } } return result; } }