小学生都能看懂的题解 | #滑动窗口的最大值#

解释算法

假设你有一排数字卡片，比如 [2, 3, 4, 2, 6, 2, 5, 1]，你要用一个特定长度（比如长度为3）的尺子从左到右移动，每次移动一格，找出尺子下面最大的数字，尺子记录的是数字的位置，而不是数字本身。

步骤如下：

准备工具：
我们需要一个尺子（滑动窗口），还需要一个记录最大数字的本子（ArrayList）。
初始化：
开始时，尺子放在最左边，记录下尺子下面的最大数字。
移动尺子：
每向右移动一格，我们需要检查尺子下面的新数字是不是比之前记录的大，如果是，就更新我们的记录。
记录最大值：
每移动一格后，记录下当前尺子下的最大值。
重复步骤：
继续向右移动尺子，直到不能再移动为止。

代码实现

现在让我们把这些步骤变成代码。我们会用一个特殊的尺子——一个叫做 Deque 的东西，它可以方便地在两头加东西和删东西。这里我们用 LinkedList 来实现 Deque。

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class Solution {
    public List<Integer> maxInWindows(int[] num, int size) {
        // 如果输入的数据有问题，直接返回一个空列表
        if (num == null || num.length == 0 || size <= 0) {
            return new ArrayList<>();
        }
        
        // 创建一个列表用来存储结果
        List<Integer> result = new ArrayList<>();
        
        // 创建一个特殊的尺子（Deque）
        LinkedList<Integer> deque = new LinkedList<>();
        
        // 遍历每一个数字
        for (int i = 0; i < num.length; i++) {
            // 如果尺子太长（前面的数字已经不在窗口内），删除尺子前面的部分
            while (!deque.isEmpty() && deque.peekFirst() <= i - size) {
                deque.removeFirst();
            }
            
            // 如果尺子后面有比当前数字小的，删除它们
            while (!deque.isEmpty() && num[deque.peekLast()] < num[i]) {
                deque.removeLast();
            }
            
            // 把当前数字的位置加到尺子后面
            deque.addLast(i);
            
            // 如果尺子刚好覆盖了指定的数量的数字，记录当前最大值
            if (i >= size - 1) {
                result.add(num[deque.peekFirst()]);
            }
        }
        
        // 返回记录的结果
        return result;
    }
}

代码解释

初始化：
首先检查输入是否有效，如果不合法就直接返回空列表。
创建结果容器：
创建一个 ArrayList 用于存储每一步的最大值。
创建特殊尺子：
使用 LinkedList 来模拟一个双端队列（Deque），它可以快速地在前后添加和移除元素。
遍历数组：
通过一个循环遍历数组中的每一个元素。
清理尺子：
如果尺子前面的数字已经不在窗口内了（即移动了一步之后，尺子前面的数字不再被需要），就把它移除。
移除比当前数字小的：
如果尺子后面的数字比当前数字小，那这些数字肯定不会成为最大值，所以把它们移除。
添加当前数字：
把当前数字的位置加入尺子后面。
记录最大值：
如果尺子已经移动到了正确的位置（即覆盖了指定数量的数字），记录尺子前面的数字作为当前的最大值。
返回结果：
完成遍历后，返回记录的结果列表。

如果这篇文章对你有帮助，请点个免费的赞👍，让它能够帮助更多的人。