跳到主要内容

滑动窗口算法

什么是滑动窗口？​

想象你透过一扇窗户看外面的风景，这扇窗户就是"滑动窗口"。你可以：

  • 左右移动窗户：看到不同的风景
  • 调整窗户大小：看到更多或更少的内容

在编程中，滑动窗口就是在数组上移动的一个"框"，用来观察不同位置的数据。

解决什么问题？​

核心问题：避免重复计算，提高效率！

暴力方法的问题​

假设我们要找数组中长度为3的子数组的最大和：

// 暴力方法 - 很慢！
func maxSum_暴力(nums []int, k int) int {
    maxSum := 0
    
    // 对每个可能的起始位置
    for i := 0; i <= len(nums)-k; i++ {
        sum := 0
        // 重新计算这个窗口的和
        for j := i; j < i+k; j++ {
            sum += nums[j]  // 每次都要重新加一遍
        }
        if sum > maxSum {
            maxSum = sum
        }
    }
    
    return maxSum
}

问题：每次都重新计算整个窗口，很多计算是重复的！

滑动窗口的优化​

// 滑动窗口 - 很快！
func maxSum_滑动窗口(nums []int, k int) int {
    // 先算第一个窗口
    sum := 0
    for i := 0; i < k; i++ {
        sum += nums[i]
    }
    maxSum := sum
    
    // 然后窗口一步步移动
    for i := k; i < len(nums); i++ {
        // 关键：只需要减去左边的，加上右边的
        sum = sum - nums[i-k] + nums[i]
        if sum > maxSum {
            maxSum = sum
        }
    }
    
    return maxSum
}

滑动过程详细演示​

让我们用一个具体例子来看滑动窗口的移动过程：

数组：[1, 3, 2, 6, 1, 4, 5]，窗口大小：3

可变窗口：找最长无重复子串​

有时候窗口大小需要变化。比如找字符串中最长的无重复字符子串。

例子：字符串 "abcabcbb"

简单代码实现：

func lengthOfLongestSubstring(s string) int {
    left := 0
    maxLen := 0
    charPos := make(map[byte]int)  // 记录每个字符的位置
    
    for right := 0; right < len(s); right++ {
        char := s[right]
        
        // 如果字符重复了，移动左指针
        if pos, exists := charPos[char]; exists && pos >= left {
            left = pos + 1  // 跳过重复的字符
        }
        
        charPos[char] = right       // 更新字符位置
        currentLen := right - left + 1
        if currentLen > maxLen {
            maxLen = currentLen     // 更新最大长度
        }
    }
    
    return maxLen
}

滑动窗口的两种类型​

固定窗口​

特点：窗口大小不变，只是位置移动 用途：求固定长度子数组的最值、平均值等

// 模板
func fixedWindow(nums []int, k int) {
    // 1. 计算第一个窗口
    for i := 0; i < k; i++ {
        // 处理 nums[i]
    }
    
    // 2. 滑动窗口
    for i := k; i < len(nums); i++ {
        // 移除 nums[i-k]
        // 加入 nums[i]
        // 更新结果
    }
}

可变窗口​

特点：窗口大小会变化 用途：寻找满足条件的最长/最短子数组

// 模板
func variableWindow(nums []int) {
    left := 0
    
    for right := 0; right < len(nums); right++ {
        // 加入 nums[right] 到窗口
        
        for /* 窗口不满足条件时 */ {
            // 移除 nums[left] 从窗口
            left++
        }
        
        // 更新结果
    }
}

为什么滑动窗口这么快？​

时间复杂度对比：

举例说明：

  • 数组长度 n=1000，窗口大小 k=100
  • 暴力方法：1000 × 100 = 100,000 次运算
  • 滑动窗口：1000 次运算
  • 快了100倍！

常见应用场景​

  1. 数据分析：计算股票的移动平均线
  2. 网络传输：TCP协议的滑动窗口控制流量
  3. 字符串处理：查找最长/最短满足条件的子串
  4. 算法题：各种子数组/子串问题

TCP中的滑动窗口机制​

在网络通信中，TCP协议使用滑动窗口来实现流量控制和拥塞控制，确保数据传输的可靠性和效率。

TCP滑动窗口的基本概念​

TCP滑动窗口不是在数组上滑动，而是在数据流上滑动，用来控制：

  • 发送多少数据（发送窗口）
  • 接收多少数据（接收窗口）
  • 网络能承受多少数据（拥塞窗口）

流量控制（Flow Control）​

目的：防止发送方发送数据太快，让接收方来不及处理

接收窗口机制​

// 模拟TCP接收窗口
type TCPReceiver struct {
    buffer     []byte    // 接收缓冲区
    bufferSize int       // 缓冲区总大小
    dataInBuffer int     // 当前缓冲区中的数据量
    windowSize int       // 当前可接收的窗口大小
}

func (r *TCPReceiver) updateWindow() int {
    // 窗口大小 = 缓冲区剩余空间
    r.windowSize = r.bufferSize - r.dataInBuffer
    return r.windowSize
}

func (r *TCPReceiver) receiveData(data []byte) bool {
    if len(data) > r.windowSize {
        return false  // 窗口太小，拒绝接收
    }
    
    // 接收数据到缓冲区
    copy(r.buffer[r.dataInBuffer:], data)
    r.dataInBuffer += len(data)
    
    // 更新窗口大小
    r.updateWindow()
    return true
}

流量控制时序图​

拥塞控制（Congestion Control）​

目的：防止网络拥塞，根据网络状况动态调整发送速度

拥塞窗口的演进​

TCP拥塞控制有四个阶段：

1. 慢启动（Slow Start）​

// 模拟TCP慢启动
type CongestionControl struct {
    cwnd      int  // 拥塞窗口大小
    ssthresh  int  // 慢启动阈值
    state     string
}

func (cc *CongestionControl) slowStart() {
    // 每收到一个ACK，cwnd增加1
    // 实际效果：每个RTT窗口翻倍
    cc.cwnd += 1
    
    if cc.cwnd >= cc.ssthresh {
        cc.state = "congestion_avoidance"
    }
}

2. 拥塞避免（Congestion Avoidance）​

func (cc *CongestionControl) congestionAvoidance() {
    // 每收到一个ACK，cwnd增加 1/cwnd
    // 实际效果：每个RTT窗口增加1
    increment := 1.0 / float64(cc.cwnd)
    cc.cwnd += int(increment)
}

3. 拥塞发生时的处理​

func (cc *CongestionControl) onCongestion(isTimeout bool) {
    if isTimeout {
        // 超时：回到慢启动
        cc.ssthresh = cc.cwnd / 2
        cc.cwnd = 1
        cc.state = "slow_start"
    } else {
        // 3个重复ACK：快恢复
        cc.ssthresh = cc.cwnd / 2
        cc.cwnd = cc.ssthresh + 3
        cc.state = "fast_recovery"
    }
}

拥塞控制完整时序图​

拥塞窗口变化图​

滑动窗口的协调工作​

实际的TCP发送窗口是三个窗口的最小值：

func calculateSendWindow(
    receiverWindow int,    // 接收方通告的窗口
    congestionWindow int,  // 拥塞控制窗口
    advertiseWindow int,   // 通告窗口
) int {
    // 实际发送窗口 = min(接收窗口, 拥塞窗口)
    sendWindow := receiverWindow
    if congestionWindow < sendWindow {
        sendWindow = congestionWindow
    }
    return sendWindow
}

完整的TCP窗口控制流程​

实际应用效果​

TCP滑动窗口机制带来的好处：

  1. 流量控制：

    • 防止接收方缓冲区溢出
    • 自适应接收方的处理能力

  2. 拥塞控制：

    • 防止网络拥塞
    • 公平共享网络带宽
    • 最大化网络利用率

  3. 可靠传输：

    • 保证数据按序到达
    • 自动重传丢失的数据

性能对比：

  • 没有流量控制：可能导致数据丢失，需要大量重传
  • 没有拥塞控制：网络拥塞时性能急剧下降
  • 使用滑动窗口：在可靠性和效率间找到最佳平衡

这就是为什么TCP能成为互联网最重要的传输协议之一 - 滑动窗口机制让它既可靠又高效！