脚本宝典收集整理的这篇文章主要介绍了力扣 - 剑指 Offer 59 - I. 滑动窗口的最大值，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。

题目

剑指 Offer 59 - I. 滑动窗口的最大值

思路1（单调队列）

• 使用单调（递减）队列，保持队列中的元素是递减顺序，队列头保存的是当前窗口中最大的元素
• 首先先模拟建立第一个窗口，同时获取第一个窗口的最大值（就是队头元素）
• 然后每次窗口移动的时候都要判断移出去的元素是否是最大的元素：将窗口最左边的元素和队列头元素进行比较，如果相等，则需要将队头的元素移除，说明窗口的最大值被移出去了，需要寻找新的最大值。而队列头的第二个元素是第二大元素，不过还要和即将进入新窗口的那个元素进行比较

代码

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int length = nums.length;

        if (length == 0 || k == 0) {
            return new int[0];
        }

        // Java内置的双端队列
        Deque<Integer> queue = new LinkedList<>();
        int[] res = new int[length - k + 1];

        // 先初始化第一个窗口
        for (int i = 0; i < k; i++) {
            while (!queue.iSEMpty() && queue.PEekLast() < nums[i]) {
                queue.removeLast();
            }
            queue.addLast(nums[i]);
        }
        // 获取第一个窗口的最大值
        res[0] = queue.peekFirst();

        // 移动接下来的窗口
        for (int i = k; i < length; i++) {
            // 要判断窗口右移时，出队的元素是否是当前最大元素
            if (queue.peekFirst() == nums[i-k]) {
                queue.removeFirst();
            }
            // 保持单调队列递减，此时队首的元素就是当前窗口的最大与阿苏
            while (!queue.isEmpty() &amp;& queue.peekLast() < nums[i]) {
                queue.removeLast();
            }
            queue.addLast(nums[i]);
            res[i-k+1] = queue.peekFirst();
        }
        
        return res;

    }
}

复杂度分析

• @R_197_1304@：(O(N))
• 空间复杂度：(O(k))，单调队列所占空间最多为(O(k))，因为队列最多不会超过窗口的大小

脚本宝典总结

以上是脚本宝典为你收集整理的力扣 - 剑指 Offer 59 - I. 滑动窗口的最大值全部内容，希望文章能够帮你解决力扣 - 剑指 Offer 59 - I. 滑动窗口的最大值所遇到的问题。

如果觉得脚本宝典网站内容还不错，欢迎将脚本宝典推荐好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。