每日练习与编程练习

我会先把任务建模成预算约束下的单调子模最大化，而不是简单取 top-K 相关帧。top-K 容易集中在同一个镜头，导致长视频问答漏掉关键前后文。候选集合先通过 ANN 从视觉、OCR、ASR 三路召回，得到规模为 M 的候选帧/片段，例如 M=500~2000，再在候选集上做预算选择。目标函数可以定义为：F(S)=α·Σ_g max_{i∈S∩g} r_i + β·Σ_{u∈C} w_u max_{i∈S} sim(u,i) + γ·Σ_b min(1, |S∩b|)，其中第一项是按时间桶或事件簇做 capped relevance，避免重复高分帧堆叠；第二项是 facility-location coverage，让被选帧代表候选集中的视觉变化；第三项鼓励覆盖不同时间段或镜头。约束是 Σ_{i∈S} c_i≤B、|S|≤K，并可加每个镜头最多 m 帧的 partition matroid 约束。这个 F 基本是单调子模函数，适合用贪心近似。 在线方法：第一阶段多路召回，文本 query 分别检索 ASR/OCR/视觉 embedding，合并去重，并按时间扩展邻域，例如命中帧前后各取 1~2 个关键帧，防止只取到结果帧而缺少过程。第二阶段在候选集上做 lazy greedy，每次选择单位成本边际收益 ΔF(i|S)/c_i 最大的帧，直到 token 预算耗尽；若候选成本差异很大，保留 best singleton 与 greedy 结果取优。对单 knapsack 约束有常数近似，纯 cardinality 下经典贪心有 1-1/e 近似；加镜头上限时工程上用贪心加可行性检查，理论上可提到 matroid+knapsack 的连续贪心更强但线上成本高。复杂度方面，召回 ANN 约 O(log N) 或亚线性；候选集 M 上若预先只计算候选间近似相似度，lazy greedy 约 O(L log M · cost_delta)，L 是选中帧数，通常几十以内。coverage 的 max sim 可以增量维护，每选一帧更新每个候选 u 当前最大覆盖值，朴素 O(ML)，M=1000、L=64 可接受。 工程上会做几件事：一是 token 成本 c_i 要用真实 VLM patch/token 估计，不用固定帧数；二是按 query 类型动态调参，例如“什么时候发生”更重时间覆盖，“画面里有什么文字”提高 OCR 召回权重；三是给高置信短视频走简单 top relevance，以降低延迟；四是对低相关 query 或无命中情况回退到均匀分层采样；五是线上记录 selected frame、score、budget、VLM answer attribution，用于离线 replay 保持一致。边界条件包括：大量相似镜头时需要去冗余；稀有事件只有一两帧时不能被 coverage 淹没，应设置 relevance 下限或强制保留 top 相关帧；ASR/OCR 与画面错位时需要时间窗口对齐；多段答案任务要避免只选一个峰值区域。最终输出给 VLM 时应携带时间戳、来源模态和局部上下文，便于答案溯源。

参考解法如下，使用单调递减栈统计每个元素作为子数组右端点时能贡献多少个合法子数组。

python
from typing import List


class Solution:
    def numberOfSubarrays(self, nums: List[int]) -> int:
        ans = 0

        # 栈中元素为 [value, count]
        # value 单调递减，count 表示当前仍然有效的、值为 value 的元素个数
        stack = []

        for x in nums:
            # 比 x 小的元素会被 x 阻断，之后不可能再作为边界最大值
            while stack and stack[-1][0] < x:
                stack.pop()

            if stack and stack[-1][0] == x:
                # 当前 x 自己形成一个长度为 1 的子数组：+1
                # 同时可以和之前所有仍有效的相同 x 配对
                ans += stack[-1][1] + 1
                stack[-1][1] += 1
            else:
                # 没有可配对的相同值，只能贡献单元素子数组
                ans += 1
                stack.append([x, 1])

        return ans