青銅挑戰(zhàn)-滑動窗口其實很簡單

1. 滑動窗口基本思想

數(shù)組引入雙指針的背景：
很多算法會大量移動數(shù)組中的元素，頻繁移動元素會導致執(zhí)行效率低下或者超時，使用兩個變量能比較好的解決很多相關(guān)問題

數(shù)組雙指針，之前介紹過 對撞型 和 快慢型 兩種，滑動窗口思想就是快慢型的特例

滑動窗口

示例：

如下圖所示，假設窗口是3，當不斷有新數(shù)據(jù)來時，維護一個大小為3的一個區(qū)間，超過3就將新的放入，老的移走。
過程有點像火車在鐵軌上跑。原始數(shù)據(jù)：鐵軌，小區(qū)間：長度固定的火車。

有了區(qū)間，可以造題了，如找序列上連續(xù)3個數(shù)組的最大和是多少？

所謂窗口，就是建立兩個索引left和right，保持 {left,right} 之間一共有3個元素，然后一邊遍歷序列，一邊尋找，每改變一下就標記一下當前區(qū)間的最大和

掌握窗口和滑動的概念

窗口

• 兩個變量left和right之間的元素，可以理解為一個區(qū)間
• 窗口可能固定，也可能變化
  如果固定，需要先確定窗口是否越界
  如果不固定，先判斷是否滿足要求，在執(zhí)行邏輯處理

滑動

• 說明窗口是移動的，移動的是left和right兩個變量，而不是序列中的元素
• left和right變量移動時，區(qū)間內(nèi)元素發(fā)現(xiàn)變化

實際問題，窗口大小固定與不固定的兩種場景

1. 窗口大小固定：火車行駛
2. 窗口大小不固定：兩個老師帶隊學生外出，一個開路，一個斷后，中間學生。兩位老師之間的距離時大時小。

根據(jù)窗口大小固定與否，兩種類型的題

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

滑動窗口解題吃力的原因：

1. 解題最終要落實到數(shù)組，特別是邊界處理容易暈
2. 有些元素的比較、判斷比較麻煩，不僅要借助集合等工具，而且處理過程中還有一些技巧，不熟悉會導致解題難度大
3. 堆！堆結(jié)構(gòu)非常適合在流數(shù)據(jù)中找固定區(qū)間內(nèi)的最大、最小等問題。因此滑動窗口經(jīng)常和堆一起使用解決復雜的問題

滑動窗口和雙指針的區(qū)別

• 滑動窗口是雙指針的一種類型；
• 滑動窗口主要關(guān)注兩個指針之間元素的情況，應用范圍更小一些；
• 雙指針的應用范圍更大，花樣也更多。

2. 兩個入門題

2.1 子數(shù)組最大平均數(shù)

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

思路分析

典型的滑動窗口，窗口大小固定了，就是K
先讀取K個，然后逐步讓窗口向前走就可以了

代碼實現(xiàn)文章來源地址http://www.zghlxwxcb.cn/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 最長連續(xù)遞增序列

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

思路分析

方法1：滑動窗口
這是一個窗口大小變化的題目

如圖所示，實例序列 1,3,5,4,7,8,9,2 最長遞增子序列 4,7,8,9 結(jié)果應返回4

我們可以從第2個元素開始，定義 [left, right] 區(qū)間來表示當前的遞增區(qū)間，執(zhí)行如下操作

• 當前遍歷的元素比它左邊的元素大，right增加
• 否則就將left跳到right的起始位置，重新開始計算

方法2：
一邊遍歷，一邊統(tǒng)計每個遞增區(qū)間的長度，如果長度超過之前左右區(qū)間的長度，將其保留

代碼實現(xiàn)

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

到了這里，關(guān)于算法通關(guān)村第十六關(guān)：青銅挑戰(zhàn)-滑動窗口其實很簡單的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！