首页 > 其他 > 详细

力扣 - 239. 滑动窗口最大值

时间:2020-12-01 09:13:16      阅读:23      评论:0      收藏:0      [点我收藏+]

题目

239. 滑动窗口最大值

思路1(暴力)

  • 每次移动窗口都要重新遍历窗口的值来找到最大值
  • 但是超时了,所以不合题意,题目要求线性时间

代码

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int len = nums.length;
        int[] res = new int[len - k + 1];

        for (int i = 0; i < len - k + 1; i++) {
            int max = Integer.MIN_VALUE;
            for (int j = i; j < i+k; j++) {
                if (max < nums[j]) {
                    max = nums[j];
                }
            }
            res[i] = max;
        }
        return res;
    }
}

复杂度分析

  • 时间复杂度:\(O(N*k)\),其中 N 为数组长度,k 为窗口大小
  • 空间复杂度:\(O(N-k+1)\),其中 N 为数组长度,k 为窗口大小

思路2(滑动窗口+单调队列)

  • 使用单调递增队列
  • 队列中存储的是nums中对应元素的下标
  • 维护队列保持递减
  • 同时每次循环还要判断当前最大的元素(即队头位置的那个)是否超出了当前窗口的范围,如果超过了,那么就删除,这样可以保证每次窗口中都是最大值

代码

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int len = nums.length;
        int[] res = new int[len - k + 1];
        Deque<Integer> queue = new LinkedList<>();

        for (int i = 0; i < len; i++) {
            // 维护一个单调递增队列,使队列中的元素递减
            while (!queue.isEmpty() && nums[queue.peekLast()] < nums[i]) {
                queue.pollLast();
            }
            // 下一个新窗口的元素下标入队
            queue.offer(i);
            // 判断此时最大值是不是在窗口的有效范围中
            if (queue.peek() <= i-k) {
                queue.poll();
            }
            // 当i >= k-1 才开始计算结果
            if (i >= k-1) {
                res[i-k+1] = nums[queue.peek()];
            }
        }
        return res;
    }
}

复杂度分析

  • 时间复杂度:\(O(N)\),其中 N 为数组长度
  • 空间复杂度:\(O(N)\),其中 N 为数组长度

力扣 - 239. 滑动窗口最大值

原文:https://www.cnblogs.com/linzedian/p/14065693.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!