LeetCode Hot100 239.滑动窗口最大值

2023-12-18 18:57:10

题目

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

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

思路

代码

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        int[] ans = new int[n - k + 1]; // 记录结果
        Deque<Integer> q = new ArrayDeque<>(); // 双端队列   队首到队尾是递减的
        for (int i = 0; i < n; i++) {
            // 1.入
            while (!q.isEmpty() && nums[q.getLast()] <= nums[i]) {
                q.removeLast(); // 维护q的单调性
            }
            q.addLast(i); // 入队
            // 2.出( 弹出队首不在窗口内的元素 )
            if (i - q.getFirst() >= k) {
                q.removeFirst();
            }
            // 3.记录答案 
            if (i >= k - 1) {
                // 由于队首到队尾单调递减,所以窗口最大值就是队首
                ans[i - k + 1] = nums[q.getFirst()];
            }
        }
        return ans;
    }
}

滑动窗口问题三部曲

1、入

2、出

3、记录答案

文章来源:https://blog.csdn.net/qq_57349657/article/details/135068132
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。