DataWhale组队学习 leetCode task4

1. 滑动窗口算法介绍

  想象你正在用一台望远镜观察一片星空。望远镜的镜头大小是固定的，你可以通过滑动镜头来观察不同的星区。滑动窗口算法就像这台望远镜，它通过一个固定或可变大小的“窗口”来观察数组或字符串中的连续区间。

• 滑动操作：就像你移动望远镜镜头，窗口可以在数据上滑动，通常是向右移动。

• 缩放操作：如果窗口大小不固定，你可以调整镜头的大小，放大或缩小观察范围。

  滑动窗口算法利用了双指针的技巧，快指针和慢指针之间的区间就是你的“窗口”。通过这个窗口，你可以高效地找到满足某些条件的连续子区间。

2. 滑动窗口的适用范围

  滑动窗口算法特别适合解决那些需要查找满足特定条件的连续区间的问题。它可以将原本需要嵌套循环的问题转化为单循环，大大减少时间复杂度。

• 固定长度窗口：就像你使用一个固定大小的望远镜镜头，窗口大小不变。

• 不定长度窗口：镜头大小可以调整，窗口大小可变，适合寻找最大或最小的满足条件的子区间。

3. 固定长度滑动窗口

3.1 算法步骤

假设你的望远镜镜头大小固定为 window_size，你可以按照以下步骤操作：

1. 初始化：将望远镜对准星空的起点，left 和 right 指针都指向数组的第一个元素。

2. 填充窗口：向右移动 right 指针，直到窗口大小达到 window_size。

3. 判断条件：当窗口大小达到 window_size 时，检查窗口内的元素是否满足条件。

4. 滑动窗口：如果满足条件，更新最优解，然后向右移动 left 指针，保持窗口大小不变。

5. 重复操作：继续向右移动 right 指针，直到遍历完整个数组。

4. 不定长度滑动窗口

4.1 算法步骤

不定长度滑动窗口就像你调整望远镜的镜头大小，根据观察到的星区动态调整窗口大小。

1. 初始化：将望远镜对准星空的起点，left 和 right 指针都指向数组的第一个元素。

2. 扩大窗口：向右移动 right 指针，扩大窗口，直到窗口内的元素满足条件。

3. 缩小窗口：当窗口内的元素满足条件时，记录当前窗口的大小，然后向右移动 left 指针，缩小窗口，直到窗口内的元素不再满足条件。

4. 重复操作：继续向右移动 right 指针，直到遍历完整个数组。

5. 链表：像火车车厢一样连接数据

链表就像一列火车，每个车厢（节点）都连接着下一个车厢。你可以轻松地在火车中间插入或删除车厢，而不需要移动整个列车。

• 优点：插入和删除操作非常高效，不需要像数组那样移动大量元素。

• 缺点：访问元素时需要从头开始遍历，效率较低。

5.1 链表的基本操作

• 插入元素：在火车中间插入一节车厢，只需要调整前后车厢的连接。

• 删除元素：移除一节车厢，只需要将前后车厢直接连接起来。

• 查找元素：从火车头开始，一节一节地查找目标车厢。

5.2 链表的应用

链表非常适合那些需要频繁插入和删除操作的场景，比如实现队列、栈等数据结构。

总结

滑动窗口算法就像一台灵活的望远镜，帮助你高效地探索数据中的连续区间。而链表则像一列灵活的火车，让你轻松地在数据中插入和删除元素。掌握这两种数据结构，你就能在算法的世界中游刃有余，像探险家一样发现数据中的宝藏！