在实时监控与流数据处理中，经常需要快速找出滑动窗口内的最大值。滑动窗口最大值查找器 (Sliding Window Maximum Finder) 使用单调队列（双端队列）实现高效的 O(n) 时间复杂度算法，适用于实时峰值监控、流数据处理、时序数据峰值检测等场景。

本案例基于 Kotlin Multiplatform（KMP）与 OpenHarmony，实现了一个滑动窗口最大值查找器：

• 高效算法：使用单调队列实现 O(n) 时间复杂度，优于朴素方法的 O(nk)。
• 详细报告：展示每个窗口的详细信息、最大值位置、最大值序列。
• 变化追踪：自动识别最大值变化点，标注上升/下降趋势。
• 统计摘要：提供全局最大值、最小值、平均值、标准差等统计信息。

---

一、问题背景与典型场景

典型场景：

1. 实时监控峰值：监控系统指标（CPU、内存、延迟）在每个时间窗口内的峰值。
2. 流数据处理：处理连续数据流，快速找出每个窗口的最大值，用于告警与决策。
3. 时序数据峰值检测：分析时序数据，识别局部峰值与异常突刺。
4. 容量规划：通过观察窗口最大值趋势，评估系统容量需求。
5. 性能分析：在性能监控中，快速定位高负载时段。

优势：

• 高效算法：O(n) 时间复杂度，优于朴素 O(nk) 方法。
• 空间优化：仅使用 O(k) 额外空间（k 为窗口大小）。
• 实时友好：适合流式数据处理，每次窗口滑动只需 O(1) 均摊时间。
• 可扩展性强：算法框架可扩展为最小值查找、Top-K 查询等变种。

---

二、滑动窗口最大值原理拆解

滑动窗口最大值问题的核心在于：如何高效维护窗口内的最大值？

1. 朴素方法（O(nk)）

对每个窗口，遍历窗口内所有元素找最大值：

// 时间复杂度：O(nk)，其中 n 是数组长度，k 是窗口大小
for (i in 0..(n - k)) {
    val windowMax = nums.slice(i until i + k).max()
    result.add(windowMax)
}

2. 单调队列方法（O(n)）

使用双端队列维护一个单调递减的索引序列：

• 队列头部：存储当前窗口内最大值的索引。
• 队列尾部：存储可能成为未来窗口最大值的候选索引。
• 关键操作：
  1. 移除窗口外的元素（索引 < 当前窗口起始位置）。
  2. 移除队列尾部所有小于当前元素的索引（保持单调性）。
  3. 将当前元素索引加入队列尾部。
  4. 队列头部索引对应的值即为当前窗口最大值。

算法流程示例（窗口大小 k=3）：

数组: [1, 3, -1, -3, 5, 3, 6, 7]
索引:  0  1   2   3  4  5  6  7

窗口 [0,2]: 队列=[1,2] → 最大值=3 (索引1)
窗口 [1,3]: 队列=[2] → 最大值=3 (索引1，但索引1已出窗，移除后队列=[2]，最大值=-1)

实际上更精确的处理：

i=0: 窗口[0-2], 队列维护索引，保持单调递减
  - 队列: [1,2] (值: [3,-1])
  - 最大值: nums[1]=3

i=1: 窗口[1-3]
  - 移除索引0（已出窗）
  - 队列: [1,2] → [2] (因为-3小于-1，无需移除)
  - 最大值: nums[1]=3

i=2: 窗口[2-4]
  - 移除索引1（已出窗）
  - 队列: [2] → [4] (5大于-1，移除索引2)
  - 最大值: nums[4]=5

3. 复杂度分析

• 时间复杂度：O(n) - 每个元素最多入队和出队一次。
• 空间复杂度：O(k) - 队列最多存储 k 个索引（窗口大小）。

---

三、Kotlin 滑动窗口最大值引擎

1. 输入格式设计

统一文本输入：

window=3
series=1,3,-1,-3,5,3,6,7

• window：窗口大小（整数，默认 3，最小 1）。
• series：数值序列，逗号/空格/分号分隔。

2. 核心算法实现 (slidingWindowMaximumFinder)

@JsExport
fun slidingWindowMaximumFinder(inputData: String): String {
    // 解析输入参数
    var windowSize = 3
    val values = mutableListOf<Double>()
    
    // ... 解析逻辑 ...
    
    // 使用单调队列（双端队列）优化
    val deque = ArrayDeque<Int>()  // 存储索引，按值从大到小
    val results = mutableListOf<WindowResult>()
    
    // 处理前 windowSize 个元素，构建初始窗口
    for (i in 0 until windowSize) {
        // 移除队列尾部所有小于当前值的索引
        while (deque.isNotEmpty() && values[deque.last()] <= values[i]) {
            deque.removeLast()
        }
        deque.addLast(i)
    }
    
    // 第一个窗口的最大值
    results += WindowResult(
        startIdx = 0,
        endIdx = windowSize - 1,
        maxValue = values[deque.first()],
        maxIndex = deque.first(),
        windowValues = values.subList(0, windowSize)
    )
    
    // 滑动窗口，处理剩余元素
    for (i in windowSize until n) {
        // 移除窗口外的元素（索引 < i - windowSize + 1）
        while (deque.isNotEmpty() && deque.first() < i - windowSize + 1) {
            deque.removeFirst()
        }
        
        // 移除队列尾部所有小于当前值的索引
        while (deque.isNotEmpty() && values[deque.last()] <= values[i]) {
            deque.removeLast()
        }
        deque.addLast(i)
        
        // 当前窗口的最大值是队列头部索引对应的值
        val start = i - windowSize + 1
        results += WindowResult(
            startIdx = start,
            endIdx = i,
            maxValue = values[deque.first()],
            maxIndex = deque.first(),
            windowValues = values.subList(start, i + 1)
        )
    }
    
    // 生成报告...
}

实现要点：

• 单调队列维护：使用 ArrayDeque 存储索引，保持队列内索引对应值单调递减。
• 窗口外元素移除：每次滑动时，移除索引小于 i - windowSize + 1 的元素。
• 候选元素过滤：新元素入队前，移除所有值小于等于新元素的候选索引。
• 最大值获取：队列头部索引对应的值即为当前窗口最大值。

3. 输出格式

报告包含：

1. 摘要信息：序列长度、窗口大小、窗口数量。
2. 原始序列：完整的输入数据序列。
3. 窗口最大值详情：每个窗口的范围、内容、最大值、最大值位置。
4. 最大值序列：所有窗口最大值组成的序列。
5. 统计摘要：全局最大值、最小值、平均值、标准差。
6. 最大值变化点：标注最大值上升/下降的变化点。

示例输出：

🔍 滑动窗口最大值查找报告
━━━━━━━━━━━━━━━━━━━━━━━━━━━━
原始序列长度: 8
窗口大小: 3
窗口数量: 6

🧮 原始序列
[1, 3, -1, -3, 5, 3, 6, 7]

📊 窗口最大值详情
窗口索引 | 数据范围 | 窗口内容 | 最大值 | 最大值位置
---------|----------|----------|--------|------------
   0    | [0..2] | [1,3,-1] | 3 | 索引 1
   1    | [1..3] | [3,-1,-3] | 3 | 索引 1
   2    | [2..4] | [-1,-3,5] | 5 | 索引 4
   ...

📈 最大值序列
[3, 3, 5, 5, 6, 7]

---

四、ArkTS 前端布局与交互（pages/Index.ets）

1. 布局设计

采用垂直堆叠布局，与之前的双栏布局形成对比：

• 顶部标题栏：蓝色背景，简洁标题展示。
• 算法说明卡片：浅蓝色背景，展示算法特性与复杂度。
• 输入参数区域：白色卡片，包含输入框与快速填充按钮。
• 执行按钮：醒目的大按钮，蓝色主题。
• 加载状态：独立的加载指示器区域。
• 结果显示：白色卡片，完整展示查找结果。

2. 交互功能

• 快速填充示例：
  • “📝 基础示例”：预设基础测试数据。
  • “🎯 复杂示例”：预设复杂测试数据。
• 实时执行：点击"🚀 执行查找"后，异步调用 Kotlin 函数并显示结果。
• 状态反馈：加载中显示进度条，执行完成显示详细结果。

3. 调用方式

import { slidingWindowMaximumFinder } from './hellokjs'

private executeCase() {
  this.isLoading = true
  setTimeout(() => {
    try {
      let output: string = slidingWindowMaximumFinder(this.inputValue)
      this.result = output
    } catch (error) {
      this.result = `❌ 执行出错: ${error}`
    } finally {
      this.isLoading = false
    }
  }, 100)
}

布局改动侧重：

• 垂直堆叠：所有内容垂直排列，信息流清晰。
• 卡片式设计：使用白色卡片区分不同功能模块。
• 颜色主题：采用蓝色系（#1976D2）作为主色调，与算法特性呼应。
• 响应式布局：适配不同屏幕尺寸，内容自动换行。

---

五、工程化落地建议

1. 窗口大小选择：

   • 根据业务周期选择窗口大小（如分钟级、小时级）。
   • 小窗口（3-5）适合细粒度监控，大窗口（10-20）适合趋势分析。

2. 实时处理优化：

   • 对于流式数据，维护一个全局队列，避免重复计算。
   • 考虑使用循环缓冲区减少内存分配。

3. 扩展功能：

   • 最小值查找：修改单调队列为单调递增。
   • Top-K 查询：维护大小为 k 的优先队列。
   • 范围查询：同时维护最大值和最小值。

4. 性能优化：

   • 对于固定窗口大小，可预分配队列容量。
   • 大批量数据时，考虑批量处理减少状态更新。

5. 监控指标：

   • 记录最大值变化频率，识别突刺模式。
   • 结合时间戳，分析峰值出现的周期性。

6. 告警策略：

   • 当窗口最大值超过阈值时触发告警。
   • 连续多个窗口最大值上升时，预警容量风险。

7. 可视化建议：

   • 绘制原始序列与最大值序列的对比图。
   • 标注最大值变化点，突出峰值区域。

8. 真实场景对接：

   • 从监控系统提取时序数据。
   • 按业务周期（分钟/小时）设置窗口大小。
   • 结合告警系统，实现自动峰值检测。

---

六、算法变种与应用

1. 滑动窗口最小值

只需将单调队列改为单调递增：

// 移除队列尾部所有大于当前值的索引
while (deque.isNotEmpty() && values[deque.last()] >= values[i]) {
    deque.removeLast()
}

2. 滑动窗口中位数

使用两个堆（大顶堆 + 小顶堆）维护中位数。

3. 滑动窗口 Top-K

使用大小为 k 的优先队列（最小堆）。

4. 应用场景扩展

• 股票价格分析：找出每个时间窗口内的最高价。
• 网络流量监控：监控每个时间段的峰值流量。
• 服务器负载分析：识别高负载时段。
• 传感器数据：检测传感器读数的峰值。

---

七、快速检查清单

• 输入格式正确：window=数字 和 series=数值序列。
• 窗口大小验证：窗口大小不能大于序列长度。
• 单调队列维护：队列内索引对应值保持单调递减。
• 窗口外元素移除：每次滑动时正确移除过期索引。
• 最大值获取准确：队列头部索引对应值即为最大值。
• 变化点识别：正确标注最大值上升/下降的变化。
• 统计信息完整：提供全局最大值、最小值、平均值等。
• UI 布局清晰：垂直堆叠，卡片式设计，信息流清晰。
• 示例加载功能正常：快速填充预设测试数据。
• 错误处理完善：空输入、格式错误等情况有友好提示。

---

八、总结

滑动窗口最大值查找器通过单调队列实现了高效的 O(n) 算法，帮助我们：

• 快速定位峰值：在实时监控中快速找出每个窗口的最大值。
• 流式处理友好：适合连续数据流的实时处理。
• 可扩展性强：算法框架可扩展为最小值、Top-K 等变种。
• 工程化实用：在 AIOps、监控系统、数据分析中广泛应用。

结合 KMP 与 OpenHarmony，我们实现了轻量级的滑动窗口最大值查找器，为实时监控与流数据处理提供了有力的工具支持。

欢迎加入开源鸿蒙跨平台社区：https://openharmonycrossplatform.csdn.net