【重点】【单调队列】【滑动窗口】239.滑动窗口最大值-CSDN博客

本文链接：https://blog.csdn.net/Allenlzcoder/article/details/134796109

博客围绕239.滑动窗口最大值问题展开，涉及Python和Java语言。解题思路基于单调队列，队尾淘汰年轻且能力强时更早入职但能力差的元素，队首元素若超出滑动窗口范围则直接淘汰，还可参考剑指offer相关面试题。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

Python

思路：
（1）队尾只要有更年轻（i越靠后）同时还能力更强（数值越大）的，留着其他比它更早入职同时能力却更差的没有什么意义，统统开了；
（2）队首的虽然能力最强，但是年龄最大，一旦发现它超过年龄范围（不在滑动窗口的范围内），不用看能力就可以直接开了。

# 写法1：queue中存值
class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        res = []
        n = len(nums)
        queue = collections.deque()
        for i in range(k):
            while queue and queue[-1] < nums[i]:
                queue.pop()
            queue.append(nums[i])
        res.append(queue[0])
        for i in range(k, n):
            while queue and queue[-1] < nums[i]:
                queue.pop()
            queue.append(nums[i])
            if queue[0] == nums[i-k]:
                queue.popleft()
            res.append(queue[0])

        return res
        
# 写法2：queue中存索引
class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        res = list()
        q = collections.deque()
        for i in range(k):
            while len(q) > 0 and nums[q[-1]] < nums[i]:
                q.pop()
            q.append(i)
        res.append(nums[q[0]])
        for i in range(k, len(nums)):
            while len(q) > 0 and nums[q[-1]] < nums[i]:
                q.pop()
            q.append(i)
            if i - q[0] >= k:
                q.popleft()
            res.append(nums[q[0]])
        return res

Java

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        Deque<Integer> queue = new LinkedList<>();
        List<Integer> resList = new ArrayList<>();
        int i = 0;
        while (i < k && i < nums.length) {
            while (!queue.isEmpty() && queue.peekLast() < nums[i]) {
                queue.pollLast();
            }
            queue.offerLast(nums[i]);
            ++i;
        }
        resList.add(queue.peekFirst());
        while (i < nums.length) {
            int addVal = nums[i];
            int deleteVal = nums[i - k];
            if (queue.peekFirst() == deleteVal) {
                queue.pollFirst();
            }
            while (!queue.isEmpty() && queue.peekLast() < nums[i]) {
                queue.pollLast();
            }
            queue.offerLast(nums[i]);
            resList.add(queue.peekFirst());
            ++i;
        }

        int[] resArray = new int[resList.size()];
        for (int j = 0; j < resList.size(); ++j) {
            resArray[j] = resList.get(j);
        }

        return resArray;
    }
}

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int[] res = new int[nums.length - k + 1];
        Deque<Integer> q = new LinkedList<>();
        int inx = 0;
        while (inx < k) {
            if (q.isEmpty()) {
                q.offerLast(nums[inx++]);
            } else {
                while (!q.isEmpty() && q.peekLast() < nums[inx]) {
                    q.pollLast();
                }
                q.offerLast(nums[inx++]);
            }
        }
        res[0] = q.peekFirst(); // inx - k
        while (inx < nums.length) {
            int d = nums[inx - k];
            if (q.peekFirst() == d) {
                q.pollFirst();
            }
            while (!q.isEmpty() && q.peekLast() < nums[inx]) {
                q.pollLast();
            }
            q.offerLast(nums[inx++]);
            res[inx - k] = q.peekFirst();
        }

        return res;
    }
}