滑動窗口

什么是滑動窗口

滑動窗口是一種常用的技術，主要用于處理連續數據序列（如數組、字符串或時間序列數據），通過動態調整一個固定大小的“窗口”來高效地解決問題。窗口在序列上“滑動”，每次移動一個位置，從而避免重復計算，優化時間和空間復雜度。該技術在算法設計、網絡通信、數據分析等領域有廣泛應用。

示例

我們通過一道題來學習滑動窗口

首先我們閱讀題目,思考三個部分內容

• 已知條件
• 求什么
• 關鍵字
  已知條件為n個元素大小的數組,和一個整數k
  求平均數
  關鍵字: 平均數最大,長度為k,連續子數組
  這里,長度為k就是窗口大小為k,我們以第一個例子[1,12,-5,-6,50,3] k = 4為例子

步驟

• 確定窗口大小
• 確定窗口的起點,終點
• 確定元素進入,離開窗口時的狀態
• 更新窗口的狀態
• 得到答案
  這道題中大小為k,起點為0,終點為數組大小,元素進入和離開窗口時都是不變的,那么這里最關鍵的一步就是怎么更新窗口的狀態我們來詳細講解
• 看我們需要什么
• 在窗口中能得到什么
• 什么時候更新窗口的元素
• 怎么更新窗口的元素
  由題意不難得知我們需要窗口中元素的和(k固定,得到和就得到平均數)
  我們能在窗口中得到每個元素的值
  當我們計算完和之后就可以更新窗口的值
  由題意由于是定長k,并且求k這個窗口中sum的最大值,我們不難發現只需要每次讓窗口向前移動一位就行
  那么這道題的思考就完成了,下面看圖解
  
  這里0 - 4是第一個窗口,我們可以得到0 - 4這個窗口的和為2,平均值為0.5
  這時我們移動窗口,讓窗口到1 - 5這時和為51,以此類推,到了最后到達2,6后此時窗口的尾指針到達數組邊界,此時滑動窗口結束

代碼

 pub fn find_max_average(nums: Vec<i32>, k: i32) -> f64 {//計算第一次平均值let avg_and_sum = Self::average(&nums, 0, k);let mut avg = avg_and_sum.0;let mut sum = avg_and_sum.1;let mut res = avg;for i in 1..nums.len() {if i + k as usize > nums.len() {break;}sum -= nums[i - 1];sum += nums[i + k  as usize -1];avg = sum as f64 / k as f64;if res < avg {res = avg;}}res}fn average(nums: &Vec<i32>, start: i32, end: i32) -> (f64, i32) {let mut sum = 0.0;for i in start..end {sum += nums[i as usize] as f64;}(sum / (end - start) as f64, sum as i32)}