算法通关村第十六关:青铜挑战-滑动窗口其实很简单

这篇具有很好参考价值的文章主要介绍了算法通关村第十六关:青铜挑战-滑动窗口其实很简单。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

青铜挑战-滑动窗口其实很简单

1. 滑动窗口基本思想

数组引入双指针的背景:
很多算法会大量移动数组中的元素,频繁移动元素会导致执行效率低下或者超时,使用两个变量能比较好的解决很多相关问题

数组双指针,之前介绍过 对撞型 和 快慢型 两种,滑动窗口思想就是快慢型的特例

滑动窗口

示例:

如下图所示,假设窗口是3,当不断有新数据来时,维护一个大小为3的一个区间,超过3就将新的放入,老的移走。
过程有点像火车在铁轨上跑。原始数据:铁轨,小区间:长度固定的火车。

有了区间,可以造题了,如找序列上连续3个数组的最大和是多少?

所谓窗口,就是建立两个索引left和right,保持 {left,right} 之间一共有3个元素,然后一边遍历序列,一边寻找,每改变一下就标记一下当前区间的最大和

算法通关村第十六关:青铜挑战-滑动窗口其实很简单,算法,python

掌握窗口和滑动的概念

窗口

  • 两个变量left和right之间的元素,可以理解为一个区间
  • 窗口可能固定,也可能变化
    如果固定,需要先确定窗口是否越界
    如果不固定,先判断是否满足要求,在执行逻辑处理

滑动

  • 说明窗口是移动的,移动的是left和right两个变量,而不是序列中的元素
  • left和right变量移动时,区间内元素发现变化

实际问题,窗口大小固定与不固定的两种场景

  1. 窗口大小固定:火车行驶
  2. 窗口大小不固定:两个老师带队学生外出,一个开路,一个断后,中间学生。两位老师之间的距离时大时小。

根据窗口大小固定与否,两种类型的题

  1. 固定:一般求哪个窗口的元素最大、最小、平均值、和最大、和最小等
  2. 不固定:一般求一个序列里最大、最小窗口是什么等

滑动窗口解题吃力的原因:

  1. 解题最终要落实到数组,特别是边界处理容易晕
  2. 有些元素的比较、判断比较麻烦,不仅要借助集合等工具,而且处理过程中还有一些技巧,不熟悉会导致解题难度大
  3. 堆!堆结构非常适合在流数据中找固定区间内的最大、最小等问题。因此滑动窗口经常和堆一起使用解决复杂的问题

滑动窗口和双指针的区别

  • 滑动窗口是双指针的一种类型;
  • 滑动窗口主要关注两个指针之间元素的情况,应用范围更小一些;
  • 双指针的应用范围更大,花样也更多。

2. 两个入门题

2.1 子数组最大平均数

LeetCode 643
https://leetcode.cn/problems/maximum-average-subarray-i/

思路分析

典型的滑动窗口,窗口大小固定了,就是K
先读取K个,然后逐步让窗口向前走就可以了

代码实现文章来源地址https://www.toymoban.com/news/detail-707093.html

class Solution:
    def findMaxAverage(self, nums: List[int], k: int) -> float:
        window_sum = 0
        # 第一步:求第一个窗口的和
        for i in range(k):
            window_sum += nums[i]

        # 第二步:遍历,每次右边增加一个,左边减去一个,重新计算窗口的最大值
        res = window_sum
        left = 0
        for right in range(k, len(nums)):
            window_sum = window_sum + nums[right] - nums[left]
            res = max(res, window_sum)
            left += 1
        
        return res/k
2.2 最长连续递增序列

LeetCode674
https://leetcode.cn/problems/longest-continuous-increasing-subsequence/

思路分析

方法1:滑动窗口
这是一个窗口大小变化的题目

算法通关村第十六关:青铜挑战-滑动窗口其实很简单,算法,python

如图所示,实例序列 1,3,5,4,7,8,9,2 最长递增子序列 4,7,8,9 结果应返回4

我们可以从第2个元素开始,定义 [left, right] 区间来表示当前的递增区间,执行如下操作

  • 当前遍历的元素比它左边的元素大,right增加
  • 否则就将left跳到right的起始位置,重新开始计算

方法2:
一边遍历,一边统计每个递增区间的长度,如果长度超过之前左右区间的长度,将其保留

代码实现

class Solution:
    def findLengthOfLCIS(self, nums: List[int]) -> int:
        # 方法1:滑动窗口
        res = 1
        left = 0
        for right in range(1, len(nums)):
            if nums[right] <= nums[right - 1]:
                left = right
            res = max(right - left + 1, res)
        return res
class Solution:
    def findLengthOfLCIS(self, nums: List[int]) -> int:
        # 方法2
        cur_len = 1
        res = 1
        for i in range(1, len(nums)):
            if nums[i] > nums[i-1]:
                cur_len += 1
            else:
                cur_len = 1
            res = max(res, cur_len)
        return res

到了这里,关于算法通关村第十六关:青铜挑战-滑动窗口其实很简单的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 算法通关村|青铜挑战----链表

    前言:数据结构的基础:创建+增删改查 学习目标:单链表的创建+增删改查,双链表的创建+增删改查 数据域+指针域 数据域:当前节点的元素值 指针域:当前节点保存的下一个节点的元素的地址,其中最后一个元素的指针域指向null 标准的面向对象的节点的定义: LeetCode中节

    2024年02月15日
    浏览(36)
  • [Go版]算法通关村第一关青铜——链表青铜挑战笔记

    单向链表图示: 双向链表图示: 环形单向链表图示: 环形双向链表图示: 源码地址: GitHub-golang版本 如果是单向的,需要将当前节点 定位到要插入节点的前一个节点 ,否则一旦过了将无法回头找到前一个节点 如果是双向的,将当前节点 定位到要插入节点的前一个节点、

    2024年02月13日
    浏览(39)
  • 算法通关村第一关-链表青铜挑战笔记

    平时我们一般都是用数组,每个数组都会有一个相对应的索引,这样就使得数组能够方便的调用出对应索引得到需要的数据,但是这也造成了一个问题,那就是不好在数组中插入或者删除一个数据,例如 int arr[]={1,2,4,5}如果我想在数组中的2和4中添加一个数据3 那么我们首先就

    2024年02月15日
    浏览(43)
  • 算法通关村第一关——链表青铜挑战笔记

    链表的基本单元就是 节点 ,也就是说链表是由一个一个节点构成的。 而对于节点来说,里面至少会包含一个 指针 和一个 数据元素 ,也就是如下图所示: 其中数据域用来存放数据元素,指针域用来存放指向下一个节点的指针,这样一个一个连接起来的就是链表。如下图所

    2024年02月16日
    浏览(43)
  • 《算法通关村第一关——链表青铜挑战笔记》

    链表中每个结点内部的“生态环境”。 数据域存储元素的值,指针域存放指针。 示例: c语言构造链表 可分为三步 1.创建头指针。 2.创建头结点,使头指针指向头结点。 3.循环创建结点,并使前一个结点指向当前结点。 1.)创建结点。 2.)使前一个结点指向当前结点。 3.)

    2024年02月15日
    浏览(40)
  • 算法通关村第一关———链表青铜挑战笔记

    通过类来构建节点,用next指针将节点连起来。 会有插入位置的范围问题,不能超出链表范围 会有删除位置的范围问题 构造双向链表 插入和删除都有三种情况,头中尾  

    2024年02月15日
    浏览(44)
  • 算法通关村第一关--链表青铜挑战笔记

    开始时间:2023年7月16日20:45:26 什么是链表,链表是一种通过指针串联在一起的线性结构,每一个节点由两部分组成,一个是数据域一个是指针域(存放指向下一个节点的指针),最后一个节点的指针域指向null(空指针的意思)。 链表的入口节点称为链表的头结点也就是hea

    2024年02月17日
    浏览(44)
  • 算法通关村第一关 | 链表青铜挑战笔记

    一、 什么是链表? 链表是一种比较简单、很常见的数据结构,是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。 二、链表的特点 链表是一种比较简单、很常见的数据结构,是线性表(List)的一种,是一种物理存

    2024年02月14日
    浏览(38)
  • 算法通关村第一关——链表青铜挑战笔记(单链表)

    在LeeCode中一般这样创建链表 要注意创建一个变量来遍历,不要把head丢掉了 count position - 1可以方便操作,还能防止下标越界(cur为null)

    2024年02月15日
    浏览(39)
  • 【无标题】算法通关村第一关——链表青铜挑战笔记

    算法通关村第一关——链表青铜挑战笔记 C语言是如何构造出链表的 0.定义节点结构 1.建立头指针 2.建立temp指针 3.将节点连起来 3.1 把p指向temp 3.2 设立循环节点a+temp指向a+temp变为a

    2024年02月15日
    浏览(36)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包