剑指Offer系列（java版，详细解析）59.队列的最大值
题目描述
剑指 Offer 59 - I. 滑动窗口的最大值
难度困难240收藏分享切换为英文接收动态反馈
给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。
示例:
输入: 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 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
提示：
你可以假设 k 总是有效的，在输入数组不为空的情况下，1 ≤ k ≤ 输入数组的大小。
注意：本题与主站 239 题相同：https://leetcode-cn.com/problems/sliding-window-maximum/
测试用例
- 功能测试（输入数组的数字大小无序；输入数组额数字单调递增；输入数组的数字单调递减）
- 边界值测试（滑动窗口的大小为0、1、等于输入数组的长度、大于输入数组的长度）
- 特殊输入测试（输入数组为空）
题目考点
- 考察应聘者分析问题的能力。
解题思路
利用一个双端队列（存数组下标），并永远保持队首为最大值。
在过程中需要保证两点：
- 队列中后面的元素可以比前面小，因为当前面的元素在滑出窗口的时候，后面小的元素可能是最大值。
- 队列中的数组首尾存的下标的差值不能大于等于活动窗口大小，因为滑动窗口在那。
示例见书本
参考解题
class MaxQueue {
Queue<Integer> queue;
Deque<Integer> deque;
public MaxQueue() {
queue = new LinkedList<>();
deque = new LinkedList<>();
}
public int max_value() {
return deque.isEmpty() ? -1 : deque.peekFirst();
}
public void push_back(int value) {
queue.offer(value);
while(!deque.isEmpty() && deque.peekLast() < value)
deque.pollLast();
deque.offerLast(value);
}
public int pop_front() {
if(queue.isEmpty()) return -1;
if(queue.peek().equals(deque.peekFirst()))
deque.pollFirst();
return queue.poll();
}
}