LeetCode239. 滑动窗口最大值🌟🌟🌟🌟困难

算法系统课免费

课后作业

问题描述

给你一个整数数组 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 <= 105
-104 <= nums[i] <= 104
1 <= k <= nums.length

代码实现

Java

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

        for(int i = 0 ; i < nums.length; i++){
            while(!deque.isEmpty() && nums[deque.peekLast()] <= nums[i]){
                deque.pollLast();
            }

            deque.add(i);

            if(i - deque.peek() >= k){
                deque.poll();
            }

            if(i + 1 >= k){
                res[index++] = nums[deque.peek()];
            }
        }

        return res;
    }
}

Python

class Solution(object):
    def maxSlidingWindow(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """
        deque = collections.deque()
        res = []

        for i in range(len(nums)):
            while deque and nums[deque[-1]] <= nums[i]:
                deque.pop()

            deque.append(i)

            if deque[0] == i-k:
                deque.popleft()

            if i >= k-1:
                res.append(nums[deque[0]])

        return res

C++

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        deque<int> q;
        vector<int> res;

        for(int i = 0; i < nums.size(); i++){
            while(!q.empty() && nums[q.back()] <= nums[i]){
                q.pop_back();
            }

            q.push_back(i);

            if(q.front() == i-k){
                q.pop_front();
            }

            if(i >= k-1){
                res.push_back(nums[q.front()]);
            }
        }

        return res;
    }
};

Go

func maxSlidingWindow(nums []int, k int) []int {
    var q []int
    res := []int{}

    for i := 0; i < len(nums); i++ {
        for len(q) > 0 && nums[q[len(q)-1]] <= nums[i] {
            q = q[:len(q)-1]
        }

        q = append(q, i)

        if q[0] == i-k {
            q = q[1:]
        }

        if i >= k-1 {
            res = append(res, nums[q[0]])
        }
    }

    return res
}

class Solution { public int[] maxSlidingWindow(int[] nums, int k) { int n = nums.length; Deque<int[]> dq = new LinkedList<>();; for (int i = 0; i < k; i++) { while (!dq.isEmpty() && nums[i] >= dq.peekLast()[0]) { dq.pollLast(); } dq.add(new int[]{nums[i], i}); } int[] res = new int[n - k + 1]; res[0] = dq.peek()[0]; for (int i = k; i < n; i++) { while (!dq.isEmpty() && nums[i] >= dq.peekLast()[0]) { dq.pollLast(); } while (!dq.isEmpty() && dq.peek()[1] < i-k+1) { dq.pop(); } dq.add(new int[]{nums[i], i}); res[i - k + 1] = dq.peek()[0]; //dq.add(new int[]{nums[i], i}); } return res; } }

class Solution { public int[] maxSlidingWindow(int[] nums, int k) { // 双端队列：保存当前窗口最大值的数组位置，保证队列中数组位置的数值从大到小排序 Deque<Integer> deque = new LinkedList<>(); // 结果列表res的窗口个数(n - k + 1) int res[] = new int[nums.length - k + 1]; int index = 0; for (int i = 0; i < nums.length; i ++) { // 将deque内所有<=nums[i]的元素删除 while (!deque.isEmpty() && nums[deque.peekLast()] <= nums[i]) { deque.pollLast(); } // 添加当前值对应的数组下标 deque.add(i); // 判断当前队列中队首的值是否有效 if (i - deque.peek() >= k) { deque.poll(); } // 当前窗口长度为k时，保存队列最底部的值（最大值） if (i + 1 >= k) { res[index++] = nums[deque.peek()]; } } return res; } }

class Solution { public int[] maxSlidingWindow(int[] nums, int k) { int n = nums.length; int[] result = new int[n - k + 1]; ArrayDeque queue = new ArrayDeque<>();//双向队列模拟单调队列：存储元素位置，递减 for(int i = 0; i < n; i++){ if(!queue.isEmpty() && i >= queue.peekFirst() + k){ queue.pollFirst(); } while(!queue.isEmpty() && nums[i] > nums[queue.peekLast()]){ queue.pollLast(); } queue.offer(i); if(i >= k - 1){ result[i - k + 1] = nums[queue.peekFirst()]; } } return result; } }

发表回复取消回复

后才能评论

smiler 永久会员 2023年10月12日上午11:05

打卡

泡芙永久会员 2023年9月20日下午3:16

由于队列是单调递减的，所以每次窗口变动时，只需要判断队首的值是否还在窗口中就行了。
队列中存放数组下标的值：因为要判断队首的值是否在窗口范围内，由数组下标取值很方便，而由值取数组下标不是很方便。

双端队列中存下标值，队首的值是目标值

Time：O(n)，线性遍历占用O(n)，每个元素最多仅入队和出队一次，因此单调队列deque占用O(2n)
Space：O(k)，双端队列deque最多同时存储k个元素(窗口大小）

阿尚普通 2023年8月20日上午12:33

帅气的冬瓜普通 2023年7月3日下午4:41

打卡

登录以回复

课后作业

问题描述

代码实现

Java

Python

C++

Go

发表回复 取消回复

评论(4)

付款后无法显示下载地址或者无法查看内容？

发表回复取消回复