当前位置：首页 > article >正文

LeetCode--239.滑动窗口最大值（使用双端队列解决）

article 2025/3/1 10:24:56

思路：使用双端队列维护窗口最大值。当有新的元素加入队列时，弹出前面比当前新加入元素小的元素，然后加入新元素，当获取最大值只需获得队列头的元素代表滑动窗口最大值。

何为双端队列？
接口函数如下：

public interface Deque<E> extends Queue<E>, SequencedCollection<E> {

JDK源码解释为：

一个线性集合，支持在两端插入和删除元素。deque 这个名字是 “double ended queue” 的缩写，通常发音为 “deck”。大多数 Deque implementations 对它们可以包含的元素数量没有固定限制，但此接口支持容量受限的 deques 以及没有固定大小限制的 deques 。

此接口定义了访问 deque 两端元素的方法。提供了用于插入、删除和检查元素的方法。

Deque 方法总结：下表总结了上述 12 种方法：

	第一个元素（Head）		最后一个元素（尾部）
	引发异常	特殊值	引发异常	特殊值
插入	addFirst(e)	offerFirst(e)	addLast(e)	offerLast(e)
删除	removeFirst()	pollFirst()	removeLast()	pollLast()
检查	getFirst()	peekFirst()	getLast()	peekLast()

此接口扩展了 Queue 接口。当 deque 用作队列时，会产生 FIFO （先进先出）行为。元素将添加到deque的末尾，并从开头删除。从 Queue 接口继承的方法与下表中指示的方法完全相同 Deque ：

在这里插入图片描述

Deques 也可以用作 LIFO （Last-In-First-Out）堆栈。应优先使用此接口，而不是 legacy Stack 类。当 deque 用作堆栈时，元素将从 deque 的开头推送和弹出。堆栈方法等效于 Deque 下表中所示的方法。
在这里插入图片描述

代码及其思路：

public int[] maxSlidingWindow(int[] nums, int k) {
    int[] ans = new int[nums.length-k+1];
    int count = 0;
    // 使用双端队列
    Deque<Integer> queue = new ArrayDeque<>();
    for (int i = 0; i < nums.length; i++) {
        // 如果队列不为空，且当前元素大于队列最后一个元素，则将队列最后一个元素出队
        while (!queue.isEmpty() && nums[queue.getLast()] <= nums[i]) {
            queue.removeLast();
        }
        // 将当前元素的下标入队
        queue.addLast(i);
        // 如果队列第一个元素已经不在滑动窗口内，则将队列第一个元素出队
        if (i-queue.getFirst() >= k) {
            queue.removeFirst();
        }
        // 如果滑动窗口内元素个数等于k，则将当前滑动窗口内的最大值ans[count++]
        if (i >= k-1) {
            ans[count++] = nums[queue.getFirst()];
        }
    }
    return ans;
}