滑动窗口算法

可以解决一些查找满足一定条件的连续区间的性质的问题。

动态窗口大小

• 策略：双指针+计数器
  • 不断增加右边界直到满足
  • 不断增加左边界直到不满足

尽可能使字符串相等

LeetCode.1208 尽可能使字符串相等

构造一个动态大小的滑动窗口，由于总开销应当小于等于该预算，临界条件就是 cost == maxCost

class Solution {
public:
  int equalSubstring(string s, string t, int maxCost) {
    int n = s.size();
    vector<int> cost(n);
    for (int i = 0; i < n; ++i) {
      cost[i] = abs(s[i] - t[i]);
    }
 
    int left = 0, right = 0, currentCost = 0, maxLength = 0;
 
    while (right < n) {
      currentCost += cost[right];
      while (currentCost > maxCost) {
        currentCost -= cost[left];
        left++;
      }
      maxLength = max(maxLength, right - left + 1);
      right++;
    }
 
    return maxLength;
  }
};

impl Solution {
    pub fn equal_substring(s: String, t: String, max_cost: i32) -> i32 {
        let n = s.len();
        let costs: Vec<i32> = s
            .chars()
            .zip(t.chars())
            .map(|(s, t)| (s as i32 - t as i32).abs())
            .collect();
 
        let mut left = 0;
        let mut right = 0;
        let mut cost = 0;
        let mut max_length = 0;
 
        for right in 0..n {
            cost += costs[right];
            while cost > max_cost {
                cost -= costs[left];
                left += 1;
            }
            max_length = max_length.max(right - left + 1);
        }
 
        max_length as i32
    }
}

指向原始笔记的链接

“静态”窗口大小

原理类似，由于我们总需要有一个指针（例如 right）需要遍历完所有的节点，所以只在满足条件（可以放下一个窗口）的时候开始记录就好，并且记得做好相应的尾部排除。

滑动窗口最大值

LeetCode.239 滑动窗口最大值

C++ 使用了双端队列实现维护一个 单调队列 ，该队列单调递减，从而保证队列头部就是窗口中的最大值。主要策略是：

1. 移除那些已经超出当前滑动窗口范围（[i - k + 1, i]）的元素
2. 从尾部开始移除比当前元素小的元素（不可能在后续成为最大值）
3. 插入当前元素
4. 满足条件时添加最大值

class Solution {
public:
  vector<int> maxSlidingWindow(vector<int> &nums, int k) {
    int n = nums.size();
    vector<int> result;
    if (n == 0 || k == 0)
      return result;
 
    deque<int> dq; // Store indices of elements in the current window
    for (int i = 0; i < n; ++i) {
      // Remove elements not in the current window
      if (!dq.empty() && dq.front() == i - k) {
        dq.pop_front();
      }
      // Remove elements smaller than the current element
      while (!dq.empty() && nums[dq.back()] < nums[i]) {
        dq.pop_back();
      }
      dq.push_back(i);
      // Add the maximum of the current window to the result
      if (i >= k - 1) {
        result.push_back(nums[dq.front()]);
      }
    }
    return result;
  }
};

指向原始笔记的链接