在高性能計(jì)算、數(shù)據(jù)分析、監(jiān)控系統(tǒng)等應(yīng)用中，實(shí)時(shí)處理數(shù)據(jù)流是一項(xiàng)基礎(chǔ)能力。其中一個(gè)典型的需求是：在一個(gè)不斷移動(dòng)的區(qū)間（窗口）內(nèi)，快速求出當(dāng)前區(qū)間的最大值。這就是我們今天要實(shí)現(xiàn)的算法——滑動(dòng)窗口最大值（Sliding Window Maximum） 。

一、問題描述與示例

給定一個(gè)整數(shù)數(shù)組 nums 和一個(gè)整數(shù) k（窗口大?。覀冃枰敵鲆粋€(gè)數(shù)組，表示從左到右依次滑動(dòng)窗口后，每個(gè)窗口中的最大值。

示例

輸入：
nums = [1,3,-1,-3,5,3,6,7], k = 3

輸出：
[3,3,5,5,6,7]

解釋：

• 窗口 [1,3,-1] → 最大值 3
• 窗口 [3,-1,-3] → 最大值 3
• 窗口 [-1,-3,5] → 最大值 5
• 窗口 [-3,5,3] → 最大值 5
• 窗口 [5,3,6] → 最大值 6
• 窗口 [3,6,7] → 最大值 7

二、常見解法分析

1. 暴力解法（Brute Force）

最直觀的方式是：每次滑動(dòng)窗口后，遍歷窗口中所有元素，找最大值。

func MaxSlidingWindowBrute(nums []int, k int) []int {
    var result []int
    for i := 0; i <= len(nums)-k; i++ {
        maxVal := nums[i]
        for j := i; j < i+k; j++ {
            if nums[j] > maxVal {
                maxVal = nums[j]
            }
        }
        result = append(result, maxVal)
    }
    return result
}

復(fù)雜度分析：

• 時(shí)間復(fù)雜度：O(n*k)
• 空間復(fù)雜度：O(1)

當(dāng) n 較大、k 較大時(shí)，這種方法性能較差。例如 n=10^5, k=500 時(shí)，暴力解法會(huì)非常慢。

2. 優(yōu)化解法：?jiǎn)握{(diào)隊(duì)列（Monotonic Queue）

為了提升效率，我們可以使用雙端隊(duì)列（Deque）實(shí)現(xiàn)一個(gè)單調(diào)遞減隊(duì)列。

核心思想

• 隊(duì)列存下標(biāo)，而非值；
• 隊(duì)列內(nèi)下標(biāo)對(duì)應(yīng)的值保持從隊(duì)頭到隊(duì)尾遞減，這樣隊(duì)首元素就是當(dāng)前窗口最大值；
• 每次新元素加入時(shí)：
  • 移除隊(duì)尾小于當(dāng)前值的下標(biāo)；
  • 將當(dāng)前下標(biāo)加入隊(duì)尾；
• 檢查隊(duì)首是否超出窗口范圍（deque[0] <= i - k），如果是則彈出。

這種方式保證了每個(gè)元素最多進(jìn)出隊(duì)列一次，整體時(shí)間復(fù)雜度為 O(n)。

三、Go語言代碼實(shí)現(xiàn)（單調(diào)隊(duì)列法）

package main

import (
    "fmt"
)

// MaxSlidingWindow 求解滑動(dòng)窗口最大值
func MaxSlidingWindow(nums []int, k int) []int {
    if len(nums) == 0 || k == 0 {
        return []int{}
    }

    var result []int
    deque := []int{} // 存儲(chǔ)下標(biāo)

    for i, v := range nums {
        // 1. 移除隊(duì)尾比當(dāng)前元素小的下標(biāo)
        for len(deque) > 0 && nums[deque[len(deque)-1]] < v {
            deque = deque[:len(deque)-1]
        }
        // 2. 添加當(dāng)前元素下標(biāo)
        deque = append(deque, i)

        // 3. 移除超出窗口范圍的隊(duì)首下標(biāo)
        if deque[0] <= i-k {
            deque = deque[1:]
        }

        // 4. 當(dāng)窗口形成后，將隊(duì)首對(duì)應(yīng)的值加入結(jié)果
        if i >= k-1 {
            result = append(result, nums[deque[0]])
        }
    }

    return result
}

func main() {
    nums := []int{1, 3, -1, -3, 5, 3, 6, 7}
    k := 3
    fmt.Println(MaxSlidingWindow(nums, k)) // [3 3 5 5 6 7]
}

四、關(guān)鍵步驟詳解

• 隊(duì)列存下標(biāo)而非值
  • 方便判斷是否超出窗口范圍；
  • 通過 nums[deque[0]] 獲取最大值。
• 保持遞減順序
  • 只有比當(dāng)前值大的元素才可能在未來成為最大值；
  • 小于當(dāng)前值的元素直接被淘汰。
• 滑動(dòng)與淘汰
  • 每次滑動(dòng)都要檢查隊(duì)首是否還在窗口內(nèi)；
  • 淘汰不在窗口范圍的下標(biāo)。

五、復(fù)雜度分析

• 時(shí)間復(fù)雜度：O(n)
  每個(gè)元素最多被加入和移出隊(duì)列一次。
• 空間復(fù)雜度：O(k)
  隊(duì)列最多存儲(chǔ) k 個(gè)下標(biāo)。

六、工程應(yīng)用場(chǎng)景

• 系統(tǒng)性能監(jiān)控
  • 在固定時(shí)間窗口內(nèi)找CPU利用率的峰值。
• 金融數(shù)據(jù)分析
  • 計(jì)算股票價(jià)格的滑動(dòng)最大值，用于趨勢(shì)判斷。
• 信號(hào)處理
  • 檢測(cè)信號(hào)峰值，常用于音頻分析、網(wǎng)絡(luò)流量監(jiān)控。

七、常見變種

• 滑動(dòng)窗口最小值：只需將單調(diào)遞減隊(duì)列改為遞增隊(duì)列。
• 滑動(dòng)窗口平均值/中位數(shù)：需要更復(fù)雜的數(shù)據(jù)結(jié)構(gòu)（如堆、平衡樹）。
• 二維滑動(dòng)窗口最大值：可擴(kuò)展至圖像處理，如卷積操作。

八、測(cè)試與驗(yàn)證

我們可以編寫單元測(cè)試：

func TestMaxSlidingWindow(t *testing.T) {
    tests := []struct {
        nums []int
        k    int
        want []int
    }{
        {[]int{1,3,-1,-3,5,3,6,7}, 3, []int{3,3,5,5,6,7}},
        {[]int{9,10,9,-7,-4,-8,2,-6}, 5, []int{10,10,9,2}},
    }

    for _, tt := range tests {
        got := MaxSlidingWindow(tt.nums, tt.k)
        if !reflect.DeepEqual(got, tt.want) {
            t.Errorf("nums=%v k=%d got=%v want=%v", tt.nums, tt.k, got, tt.want)
        }
    }
}

九、總結(jié)

• 滑動(dòng)窗口最大值問題是經(jīng)典的單調(diào)隊(duì)列應(yīng)用；
• 暴力解法易實(shí)現(xiàn)但性能低；
• 單調(diào)隊(duì)列解法能在 O(n) 時(shí)間內(nèi)解決問題，適合大數(shù)據(jù)場(chǎng)景；
• 掌握該技巧有助于解決其他類似的區(qū)間統(tǒng)計(jì)問題。

 到此這篇關(guān)于Go語言滑動(dòng)窗口最大值的實(shí)現(xiàn)示例的文章就介紹到這了,更多相關(guān)Go語言滑動(dòng)窗口最大值內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論