DEV Community
·
滑动窗口 || Python || 数据结构与算法
💡
原文英文，约600词，阅读约需2分钟。
📝
内容提要
滑动窗口技术是一种在数组或字符串中定义并移动窗口的算法，分为固定大小和可变大小两种。它适用于计算子数组的最大值或最小值等问题，能将时间复杂度从O(n³)降低到O(n)。
🎯
关键要点
- 滑动窗口技术是一种在数组或字符串中定义并移动窗口的算法。
- 滑动窗口分为固定大小和可变大小两种类型。
- 固定大小滑动窗口的窗口大小是固定的，移动窗口遍历数组。
- 可变大小滑动窗口在每次迭代中右指针加一，左指针在条件不满足时移动。
- 滑动窗口技术适用于计算子数组的最大值或最小值等问题。
- 滑动窗口的通用模板包括初始化左右指针和处理窗口内元素的逻辑。
- 示例：最小子数组和问题，返回和大于等于目标值的最小子数组长度。
- 暴力解法的时间复杂度为O(n³)，而滑动窗口算法的时间复杂度为O(n)。
- 使用滑动窗口算法将时间复杂度从O(n³)降低到O(n)。
➡️
