leetcode代码记录(滑动窗口最大值

简介: leetcode代码记录(滑动窗口最大值

1. 题目:

给你一个整数数组 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]

2. 我的代码:

import collections
class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        # 排除特殊情况
        if len(nums) == 1:
            return nums
        if k == 1:
            return nums

        q = collections.deque()
        result = []
        # 第一个放进去
        q.append(0)
        for i in range(1, len(nums)):
            while len(q):
                if nums[q[-1]] >= nums[i]:# 可以直接放进去
                    q.append(i)
                    break
                else: # 不可以直接放进去
                    q.pop()
                    if len(q) == 0:
                        q.append(i)
                        break

            # 保持大小
            while q[-1] - q[0] + 1 > k:
                q.popleft()

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

        return result

利用双端队列,实现单调队列。每次放入元素都检查是否可以直接放入元素,通过反复和队尾元素对比,如果放入的元素比队尾元素小,则正常放入;如果比队尾元素大,则将队尾元素pop出去,再放入。为了保持单调递减的队列。


(如果剩下的队列为空了,就不再比较了,直接放入当前元素即可)


单调递减的队列的最大值必然是队列的队头元素。放入元素完毕后还需要通过反复删除队头元素来保持滑动窗口的大小。

i >= k - 1时开始统计结果。

最开始要排除特殊情况,就是nums的长度为0或者k为0的情况,这时原封不动返回nums即可。

目录
相关文章
|
2月前
【LeetCode 26】239.滑动窗口最大值
【LeetCode 26】239.滑动窗口最大值
33 1
|
2月前
【LeetCode 04】滑动窗口法总结
【LeetCode 04】滑动窗口法总结
22 0
|
4月前
|
存储 Python
【Leetcode刷题Python】239. 滑动窗口最大值
文章介绍了两种解决LeetCode上"滑动窗口最大值"问题的方法:使用大堆树和双向递减队列,提供了详细的解析和Python代码实现。
37 0
|
6月前
|
算法 搜索推荐
力扣每日一题 6/15 滑动窗口
力扣每日一题 6/15 滑动窗口
34 1
|
6月前
|
算法
【LeetCode刷题】滑动窗口解决问题:串联所有单词的子串(困难)、最小覆盖子串(困难)
【LeetCode刷题】滑动窗口解决问题:串联所有单词的子串(困难)、最小覆盖子串(困难)
|
6月前
|
算法 容器
【LeetCode刷题】滑动窗口解决问题:水果成篮、找到字符串中所有字母异位词
【LeetCode刷题】滑动窗口解决问题:水果成篮、找到字符串中所有字母异位词
|
5月前
|
存储 算法
经典的滑动窗口的题目 力扣 2799. 统计完全子数组的数目(面试题)
经典的滑动窗口的题目 力扣 2799. 统计完全子数组的数目(面试题)
|
6月前
|
算法 索引
力扣随机一题 位运算/滑动窗口/数组
力扣随机一题 位运算/滑动窗口/数组
47 0
|
6月前
【LeetCode刷题】滑动窗口思想解决:最大连续1的个数 III、将x减到0的最小操作数
【LeetCode刷题】滑动窗口思想解决:最大连续1的个数 III、将x减到0的最小操作数
|
6月前
【LeetCode刷题】滑动窗口思想解决问题:长度最小的子数组、无重复字符的最长子串
【LeetCode刷题】滑动窗口思想解决问题:长度最小的子数组、无重复字符的最长子串