前段时间，某个小公司的一名程序员朋友跟我吐槽，说他入职快两年了，老板迷恋修道，还强制员工去，声称是“培训”。
你没听错，就是“修道”！问题是这还是收费的，我就问问，这世界上还有什么能比这种事更离谱的？
算法题：排列序列
你知道的，在面试中这种题目基本是不会少的，不管是做系统架构的还是做前端的，都会涉及到一些滑动窗口的操作。简单的说，窗口每次滑动一个元素，求出该窗口中的最大值。
例子
双端队列（Deque）
遍历数组中的元素，对于每个新元素，先把不可能成为最大值的元素（即那些比当前元素小的元素）从队列中删除。 如果队列的头部已经超出了当前窗口的范围，就把它移除。 每次遍历完一个元素后，队列头部的元素就是当前窗口的最大值。
Java代码实现
import java.util.Deque;
import java.util.LinkedList;
public class SlidingWindowMax {
public int[] maxSlidingWindow(int[] nums, int k) {
if (nums == null || nums.length == 0) {
return new int[0];
}
// 结果数组
int[] result = new int[nums.length - k + 1];
// 双端队列，存储数组元素的索引
Deque<Integer> deque = new LinkedList<>();
for (int i = 0; i < nums.length; i++) {
// 移除队列中不在窗口内的元素
if (!deque.isEmpty() && deque.peek() < i - k + 1) {
deque.poll();
}
// 移除队列中所有比当前元素小的元素
while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
deque.pollLast();
}
// 将当前元素的索引加入队列
deque.offer(i);
// 当窗口已经滑动完整，开始记录结果
if (i >= k - 1) {
result[i - k + 1] = nums[deque.peek()];
}
}
return result;
}
public static void main(String[] args) {
SlidingWindowMax swm = new SlidingWindowMax();
int[] nums = {1, 3, -1, -3, 5, 3, 6, 7};
int k = 3;
int[] result = swm.maxSlidingWindow(nums, k);
for (int val : result) {
System.out.print(val + " ");
}
}
}
代码解释
Deque<Integer> deque = new LinkedList<>();这里我们用双端队列来存储元素的索引，为什么要存索引？因为这样可以方便我们控制滑动窗口的范围。if (!deque.isEmpty() && deque.peek() < i - k + 1) { deque.poll(); }这个条件判断是用来检查队列中的元素是否还在当前窗口内。如果当前队列头部的元素已经不在窗口范围内了，就把它弹出。while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) { deque.pollLast(); }这个while循环负责去掉队列中那些比当前元素小的元素，因为它们不可能再成为最大值。result[i - k + 1] = nums[deque.peek()];每次滑动完窗口，我们就把队列头部的元素添加到结果数组中。
时间复杂度
空间复杂度
小结
-END-
以上，就是今天的分享了，看完文章记得右下角给何老师点赞，也欢迎在评论区写下你的留言。
