深入 Java 滑动窗口：「区间子数组个数」的窗口内条件判断

问题背景

给定整数数组 $arr$ 和区间 $[L,R]$，求满足 最大值在 $[L,R]$ 内 的连续子数组数量。例如： $$arr = [2,1,4,3],\quad L=2,\quad R=3$$ 满足条件的子数组为：$[2], [3], [2,1], [1,3]$，共 4 个。

---

核心思路：三指针滑动窗口

传统双指针无法直接处理最大值约束，采用 三指针滑动窗口：

1. 左边界指针 $left$：标记窗口起点
2. 最近合法指针 $lastValid$：记录最近满足 $arr[i] \leq R$ 的位置
3. 最近超标指针 $lastOver$：记录最近 $arr[i] \geq L$ 的位置

窗口移动规则：

• 当 $arr[right] > R$ 时：重置窗口起点（$left = right+1$）
• 当 $arr[right] \geq L$ 时：更新 $lastOver = right$
• 子数组数量 = $lastOver - left + 1$

---

数学证明

设窗口 $[left, right]$ 内：

• 子数组终点固定为 $right$
• 起点 $start$ 需满足 $left \leq start \leq lastOver$ 此时子数组最大值 $max$ 满足： $$L \leq max \leq R$$ 因 $lastOver$ 确保存在 $\geq L$ 的元素，且窗口内无 $>R$ 的元素。

---

Java 实现

public int countSubarrays(int[] arr, int L, int R) {
    int count = 0;
    int left = 0, lastOver = -1, lastValid = 0;
    
    for (int right = 0; right < arr.length; right++) {
        // 元素超标：重置窗口
        if (arr[right] > R) {
            left = right + 1;
            lastOver = right;  // 标记无效位置
            continue;
        }
        
        // 元素达到L：更新最近合法点
        if (arr[right] >= L) {
            lastOver = right;
        }
        
        // 计算以right结尾的有效子数组数
        if (lastOver >= left) {
            count += (lastOver - left + 1);
        }
    }
    return count;
}

---

复杂度分析

• 时间复杂度：$O(n)$
  单次遍历数组，每个元素仅处理一次
• 空间复杂度：$O(1)$
  仅需常数级指针变量

---

案例推演

以 $arr=[3,1,2,5,1],\ L=2,\ R=3$ 为例：

right	arr[right]	left	lastOver	新增子数组	count
0	3	0	0	[3]	1
1	1	0	0	[1], [3,1]	3
2	2	0	2	[2], [1,2], [3,1,2]	6
3	5 > 3	4	3	重置窗口（不计数）	6
4	1	4	3	[1]（因lastOver<left不计数）	6

最终结果：6（[3], [1], [2], [3,1], [1,2], [3,1,2]）

---

总结

通过维护三个关键指针：

1. $left$ 确保窗口无超标元素
2. $lastOver$ 锁定最近满足 $max \geq L$ 的位置
3. $lastValid$ 辅助窗口重置

该算法高效解决了 区间约束下的子数组计数 问题，适用于数据流处理等场景。核心在于理解：以 $right$ 结尾的有效子数组数量取决于 $lastOver$ 的位置。