攻克 Java 滑动窗口：「最长连续递增序列」的优化技巧与边界处理

问题定义

给定无序整数数组，寻找最长连续递增子序列长度。例如：
输入：$[1,3,5,4,7]$
输出：$3$（对应子序列 $[1,3,5]$）
要求时间复杂度优于 $O(n^2)$。

---

一、暴力解法瓶颈分析

传统双指针遍历：

int maxLen = 0;
for (int i = 0; i < nums.length; i++) {
    int count = 1;
    for (int j = i + 1; j < nums.length; j++) {
        if (nums[j] > nums[j-1]) count++;
        else break;
    }
    maxLen = Math.max(maxLen, count);
}

缺陷：

• 时间复杂度：$O(n^2)$
• 重复计算：当 $[i,j]$ 递增时，$[i+1,j]$ 被重复验证

---

二、滑动窗口核心思想

动态调整窗口边界：

1. 初始化窗口 $[left, right] = [0, 0]$
2. 当 $nums[right] < nums[right+1]$ 时，right 右移
3. 否则重置 $left = right$
4. 实时更新最大长度 $maxLen$

数学表达：
设窗口长度为 $L$，满足： $$ \forall k \in [left, right-1], \quad nums[k] < nums[k+1] $$ 每次移动时间复杂度：$O(1)$

---

三、关键优化技巧

1. 跳跃重置

   • 当 $nums[right] \geq nums[right+1]$ 时，直接令 $left = right + 1$
   • 避免冗余比较（传统法需回溯至 $left+1$）

2. 差分预处理
   构建差分数组：$diff[i] = nums[i] - nums[i-1]$
   窗口扩展条件简化为：$diff[right] > 0$

3. 边界压缩

   while (right < n-1 && nums[right] < nums[right+1]) {
       right++;  // 单次循环扩展到最长
   }
   maxLen = Math.max(maxLen, right - left + 1);
   left = right; // 直接跳跃
   

---

四、边界处理全方案

边界场景	处理方案	示例输入	输出
空数组	初始检查返回0	[]	0
单元素数组	窗口长度恒为1	[5]	1
全递减序列	每次窗口大小=1	[9,7,5,3]	1
末尾递增	循环终止条件 right < n-1	[1,3,5,7]	4
等值序列	重置窗口并跳过	[2,2,2]	1

---

五、最终代码实现

public int findLengthOfLCIS(int[] nums) {
    if (nums.length == 0) return 0;
    
    int left = 0, maxLen = 1;
    for (int right = 0; right < nums.length; right++) {
        // 遇到非递增时重置左边界
        if (right > 0 && nums[right] <= nums[right-1]) {
            left = right;  // 关键跳跃点
        }
        // 实时更新最大长度
        maxLen = Math.max(maxLen, right - left + 1);
    }
    return maxLen;
}

---

六、复杂度分析

• 时间复杂度：$O(n)$
  每个元素最多被访问两次（right 遍历和 left 跳跃）
• 空间复杂度：$O(1)$
  仅用常数级额外空间

---

总结

滑动窗口破解连续序列问题的核心在于：

1. 动态边界调整：通过 $left$ 的智能跳跃避免重复计算
2. 状态继承：利用已验证的递增区域减少比较次数
3. 严谨边界处理：覆盖空数组、全等值等 corner case

此方案可扩展至同类问题（如最长连续等差序列），只需修改窗口扩展条件即可。