滑动窗口解释：使用 Ruby 代码的太阳镜类比

Source: Dev.to

太阳镜类比 😎🌄

想象你站在山坡上俯瞰一段漫长的风景。风景代表你的数组或字符串，而你有一副特殊的太阳镜，只能一次看到固定的一段——这就是你的 滑动窗口。

• 进入视野：从窗口右侧进入的新元素。
• 离开视野：从窗口左侧离开的元素。
• 状态追踪：你在窗口内部跟踪一些有趣的东西（例如，和、最大值、不同元素的数量）。

与其为每个新位置重新计算所有内容，你可以 增量更新：

1. 移除离开视野的元素。
2. 添加进入视野的元素。
3. 更新结果。

不使用滑动窗口

对于每个大小为 k 的窗口，你都会从头重新计算所有内容 → 速度慢。

使用滑动窗口

随着窗口移动，你只更新状态 → 快速且高效。

示例 1：固定大小窗口的最大和

# Landscape: array of trees
arr = [1, 2, 3, 4, 5]
k   = 3

# Initial window sum
window_sum = arr[0...k].sum
max_sum    = window_sum

# Slide the window
(1..arr.length - k).each do |i|
  window_sum = window_sum - arr[i - 1] + arr[i + k - 1]
  max_sum    = [max_sum, window_sum].max
end

puts "Maximum sum of a window of size #{k}: #{max_sum}"

解释

• arr[i - 1] 离开窗口。
• arr[i + k - 1] 进入窗口。
• window_sum 通过增量方式更新，避免了完整的重新计算。

示例 2：最长子串（包含 ≤ k 个不同字符）

s = "abcba"
k = 2

count   = Hash.new(0)  # frequency of characters in the current window
left    = 0
max_len = 0

(0...s.length).each do |right|
  count[s[right]] += 1

  # Shrink window from the left while we have more than k distinct chars
  while count.size > k
    count[s[left]] -= 1
    count.delete(s[left]) if count[s[left]] == 0
    left += 1
  end

  max_len = [max_len, right - left + 1].max
end

puts "Length of longest substring with ≤ #{k} distinct characters: #{max_len}"

解释

• 通过添加 s[right] 将窗口向右扩展。
• 如果不同字符的数量超过 k，则从左侧收缩窗口，直到满足约束。
• count 维护窗口内部的状态（字符频率）。

关键要点

• 双指针（左指针和右指针）自然地表示滑动窗口。
• 关注 增量更新：添加新元素，移除旧元素，并调整跟踪的状态。
• 用太阳镜的比喻来可视化过程，有助于把看似棘手的技巧转化为直观的理解。

小技巧：先用小的、手写的例子练习太阳镜比喻，然后再把步骤转化为代码。这能强化概念，使解决滑动窗口问题更加轻松。 😎