跳至主要內容

滑动窗口最大值

linwu大约 3 分钟

滑动窗口最大值

给定一个整数数组nums和一个整数k,请找出所有滑动窗口大小为k的子数组中的最大值。

题目描述:

给定一个整数数组nums和一个整数k,请你找出所有滑动窗口大小为k的子数组中的最大值。滑动窗口是一个固定大小的窗口,它通过在数组上滑动,每次滑动一个位置,来扫描数组中的元素。你需要返回每个滑动窗口中的最大值。

示例:

输入:nums = [1,3,-1,-3,5,3,6,7],k = 3 输出:[3,3,5,5,6,7] 解释:滑动窗口的位置从左到右分别为:[1,3,-1],[3,-1,-3],[-1,-3,5],[-3,5,3],[5,3,6],[3,6,7]。每个窗口中的最大值分别为3,3,5,5,6,7。

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

解题步骤:

这个问题可以使用滑动窗口算法来解决。我们可以维护一个双端队列,队列中存储的是窗口内元素的索引。通过比较窗口内元素的值,我们可以找到每个窗口的最大值。

解题步骤如下:

  1. 创建一个双端队列deque,用于存储窗口内元素的索引。

  2. 初始化结果数组result为空数组,用于存储每个滑动窗口的最大值。

  3. 初始化指针leftright,分别指向滑动窗口的左右边界。

  4. 遍历整个数组nums,并执行以下操作:

    • 在每次遍历之前,检查队列的头部元素是否已经超出了当前窗口的范围,如果超出,则将其从队列中删除。

    • 检查当前遍历到的元素nums[i]与队列尾部元素所对应的元素nums[deque[rear]]的大小关系。如果nums[i]大于等于nums[deque[rear]],则可以确定nums[deque[rear]]不会是任何窗口的最大值,因此将其从队列尾部删除,直到队列为空或者找到一个元素大于nums[i]

    • 将当前元素的索引i添加到队列的尾部。

    • 如果窗口的起始位置(i-k+1)大于等于0,则将队列的头部元素nums[deque[front]]添加到结果数组result中,表示当前窗口的最大值。

  5. 返回结果数组result

JavaScript解题框架:

function maxSlidingWindow(nums, k) {
    let deque = []; // 双端队列
    let result = []; // 结果数组

    let left = 0;
    let right = 0;

    while (right < nums.length) {
        // 检查队列的头部元素是否已经超出了当前窗口的范围
        if (deque.length > 0 && deque[0] <= right - k) {
            deque.shift();
        }

        // 检查当前元素与队列尾部元素的大小关系
        while (deque.length > 0 && nums[right] >= nums[deque[deque.length - 1]]) {
            deque.pop();
        }

        // 将当前元素的索引添加到队列的尾部
        deque.push(right);

        // 如果窗口的起始位置大于等于0,则将队列的头部元素添加到结果数组中
        if (right >= k - 1

) {
            result.push(nums[deque[0]]);
        }

        right++;
    }

    return result;
}

在这个框架中,我们使用一个双端队列deque来存储窗口内元素的索引。我们还创建了一个结果数组result用于存储每个滑动窗口的最大值。

我们使用leftright两个指针来构建滑动窗口。在每次滑动窗口时,我们先检查队列的头部元素是否已经超出了当前窗口的范围,并进行相应的删除操作。然后,我们检查当前遍历到的元素与队列尾部元素的大小关系,进行元素的删除操作,直到队列为空或者找到一个元素大于当前元素。接着,将当前元素的索引添加到队列的尾部。如果窗口的起始位置大于等于0,则将队列的头部元素添加到结果数组中,表示当前窗口的最大值。

关注公众号

和小伙伴们一起学习

加入技术交流群

扫描二维码 备注加群