Uber OA 连续 k 月股价严格上涨：线性统计窗口

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• 输入是按月份排列的整数价格，允许相等或下降；k 为正整数。
• 每段连续且恰好 k 个月、相邻价格均严格上涨才计数；重叠区间分别计数。
• k>n 时返回 0；k=1 时每个单月窗口都满足没有违反严格递增的相邻对，故返回 n。

解题路线

1. 维护以当前位置结尾的最长严格递增连续段长度 run。若前一个价格 < 当前价格，run 加一，否则重置为 1。
2. 当 run≥k 时，当前月份作为右端点恰好对应一个长度 k 的合法窗口，计数加一。
3. 这个判定既不会遗漏重叠窗口，也不会重复计数；每个窗口都由其唯一右端点代表。

手动走一遍

[5,3,5,7,8]、k=3 的连续上升长度依次为 [1,1,2,3,4]，末尾两处达到 k，对应 [3,5,7] 与 [5,7,8]，返回 2。若中间有 5,5，长度应在第二个 5 重置。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

"""Count length-k windows whose adjacent values strictly increase."""


def count_profitable_windows(prices: list[int], k: int) -> int:
    if k <= 0:
        raise ValueError("k must be positive")
    if k > len(prices):
        return 0
    if k == 1:
        return len(prices)
    answer = 0
    increasing_run = 1
    for i in range(1, len(prices)):
        increasing_run = increasing_run + 1 if prices[i - 1] < prices[i] else 1
        if increasing_run >= k:
            answer += 1
    return answer

复杂度

只遍历价格一次，时间 O(n)，除了计数和 run 使用 O(1) 额外空间。直接检查每个窗口的所有相邻对需要 O(nk) 时间。

易错点与追问

容易失分的边界

• 严格递增要求 <，相等价格必须中断，不可写 ≤。
• 一个长为 L 的递增段贡献 max(0,L−k+1) 个重叠窗口，不是只贡献一个。
• k≤0 没有明确的月份窗口语义；示例代码报错，而非悄悄返回 n。

继续深挖

• 若要输出窗口坐标，每当 run≥k 就输出 [i−k+1,i]；输出成本另计。
• 若价格流持续到来，每个新月份 O(1) 更新 run 与累计答案，但查询不同 k 需要另行设计索引。