滑动窗口最大值

难度:

标签:

题目描述

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回 滑动窗口中的最大值 。

示例 1：

输入：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

示例 2：

输入：nums = [1], k = 1
输出：[1]

提示：

1 <= nums.length <= 10⁵
-10⁴ <= nums[i] <= 10⁴
1 <= k <= nums.length

代码结果

运行时间: 156 ms, 内存: 0.0 MB

/*
 * Problem: Find the maximum value in each sliding window of size k in the given array nums.
 * Solution: This approach leverages Java Streams to find the max value for each window.
 * Note: Streams are not the most efficient solution for this problem, but this is an illustration.
 */
import java.util.stream.IntStream;
import java.util.Arrays;
 
public class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums == null || nums.length == 0) return new int[0];
        int n = nums.length;
        return IntStream.rangeClosed(0, n - k)
            .map(i -> Arrays.stream(nums, i, i + k).max().getAsInt())
            .toArray();
    }
}

解释

方法:

该题解使用双端队列实现了单调队列，维护了一个队列存储窗口内的元素下标。通过控制队列的进出，保证队首下标对应的元素始终是当前窗口内的最大值。在窗口滑动的过程中，不断将队尾元素与当前元素比较，将小于当前元素的下标弹出，并将当前元素下标加入队尾。当窗口形成后，每次将队首元素对应的值加入输出数组中。同时，当窗口滑出某个下标时，若该下标是队首元素，则将其从队列中弹出。

时间复杂度:

O(n)

空间复杂度:

O(k)

代码细节讲解

🦆

在算法中，为什么选择使用双端队列而不是其他数据结构如数组或链表来实现这个单调队列？

▷

双端队列（deque）允许我们从两端高效地添加和删除元素，这是实现单调队列时非常重要的功能。使用双端队列，可以在O(1)时间内从队尾添加新的元素，以及从队首移除旧的元素。如果使用数组，尽管可以在末尾添加元素，但从数组的开始位置删除元素的效率较低，通常是O(n)；而链表虽然可以在两端高效地添加和删除元素，但在实际操作中，相比于双端队列，其节点的动态分配和额外的指针操作可能使得性能稍逊一筹。因此，双端队列是实现此类功能的最佳选择。

🦆

双端队列中存储的是元素的下标而不是元素的值，这样做有什么特别的优势吗？

▷

存储元素的下标而不是值有几个重要的优势。首先，通过下标可以直接访问元素的值，并且可以检查这些下标是否还在滑动窗口的范围内。这种方法特别有助于在窗口滑动时快速确定哪些元素应该从队列中移除：如果队首的下标不再位于当前窗口内，我们可以将其快速弹出。此外，这也使得在数组中移动窗口时，能够保持与原始数据的直接联系，方便操作和理解。

🦆

你如何确保队列的单调递减性在整个窗口滑动过程中得到保持？具体是通过哪些操作实现的？

▷

为了确保队列的单调递减性，每当新的元素准备加入队列时，算法会从队列的尾部开始，逐一比较已有的元素。如果队尾元素对应的值小于当前元素的值，则这些队尾元素会被连续弹出，直到遇到一个值大于或等于当前元素的值或队列为空为止。这样可以保证队列中的元素是按照从大到小的顺序排列的，队首元素始终是当前窗口的最大值。这个过程确保了每次插入操作后队列的单调递减性。

🦆

当队列中元素的下标已经不在窗口范围内时，你是如何处理的？请解释为什么需要这样做。

▷

当窗口向右移动时，窗口的起始索引也随之增加。如果队列的队首元素的下标小于当前窗口的起始索引，那么这个元素已不再属于当前窗口范围内。在这种情况下，我们需要从队列的队首移除这个下标。这样做是必要的，因为只有在队首的下标仍然位于窗口内时，我们才能保证队首元素是窗口中的最大值。这确保了输出数组中始终是每个窗口的最大值。

相关问题

最小覆盖子串

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

注意：

对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
如果 s 中存在这样的子串，我们保证它是唯一的答案。

示例 1：

输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。

示例 2：

输入：s = "a", t = "a"
输出："a"
解释：整个字符串 s 是最小覆盖子串。

示例 3:

输入: s = "a", t = "aa"
输出: ""
解释: t 中两个字符 'a' 均应包含在 s 的子串中，
因此没有符合条件的子字符串，返回空字符串。

提示：

^{m == s.length}
^{n == t.length}
1 <= m, n <= 10⁵
s 和 t 由英文字母组成

进阶：你能设计一个在 o(m+n) 时间内解决此问题的算法吗？

最小栈

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

实现 MinStack 类:

MinStack() 初始化堆栈对象。
void push(int val) 将元素val推入堆栈。
void pop() 删除堆栈顶部的元素。
int top() 获取堆栈顶部的元素。
int getMin() 获取堆栈中的最小元素。

示例 1:

输入：
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

输出：
[null,null,null,null,-3,null,0,-2]

解释：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.getMin();   --> 返回 -2.

提示：

-2³¹ <= val <= 2³¹ - 1
pop、top 和 getMin 操作总是在 非空栈 上调用
push, pop, top, and getMin最多被调用 3 * 10⁴ 次

至多包含两个不同字符的最长子串

粉刷房子 II

除自身以外数组的乘积搜索二维矩阵 II