How does the queue help solve this problem?

The queue stores the most recent k integers, allowing efficient checking of consecutive values and enabling constant-time updates as the stream progresses.

What is the best way to handle performance when k is large?

A sliding window approach using a queue ensures constant-time processing for each new integer, making it efficient even for large values of k.

What happens if we have to track multiple consecutive values?

The solution can be extended to track different target values by adjusting the data structures or adding additional logic to the queue management.

What is the time complexity of the `consec()` method?

The time complexity of `consec()` is O(1) because it only needs to check whether all values in the queue match the target value.

Can this solution be optimized further?

While the current solution is efficient, further optimizations could include using a hash table to track value counts or adjusting the sliding window logic for specific input patterns.

#2526

Medium

auto_awesome队列·driven·状态·processing

LeetCode 题解工作台

找到数据流中的连续整数

给你一个整数数据流，请你实现一个数据结构，检查数据流中最后 k 个整数是否等于给定值 value 。请你实现 DataStream 类： DataStream(int value, int k) 用两个整数 value 和 k 初始化一个空的整数数据流。 boolean consec(int …

哈希表设计队列计数数据流

题目描述

给你一个整数数据流，请你实现一个数据结构，检查数据流中最后 k 个整数是否等于给定值 value 。

请你实现 DataStream 类：

DataStream(int value, int k) 用两个整数 value 和 k 初始化一个空的整数数据流。
boolean consec(int num) 将 num 添加到整数数据流。如果后 k 个整数都等于 value ，返回 true ，否则返回 false 。如果少于 k 个整数，条件不满足，所以也返回 false 。

示例 1：

输入：
["DataStream", "consec", "consec", "consec", "consec"]
[[4, 3], [4], [4], [4], [3]]
输出：
[null, false, false, true, false]

解释：
DataStream dataStream = new DataStream(4, 3); // value = 4, k = 3 
dataStream.consec(4); // 数据流中只有 1 个整数，所以返回 False 。
dataStream.consec(4); // 数据流中只有 2 个整数
                      // 由于 2 小于 k ，返回 False 。
dataStream.consec(4); // 数据流最后 3 个整数都等于 value， 所以返回 True 。
dataStream.consec(3); // 最后 k 个整数分别是 [4,4,3] 。
                      // 由于 3 不等于 value ，返回 False 。

提示：

1 <= value, num <= 10⁹
1 <= k <= 10⁵
至多调用 consec 次数为 10⁵ 次。

lightbulb

解题思路

方法一：计数

我们可以维护一个计数器 $\textit{cnt}$ ，记录当前连续整数为 $\textit{value}$ 的个数。

调用 consec 方法时，如果 $\textit{num}$ 与 $\textit{value}$ 相等，我们将 $\textit{cnt}$ 自增 1，否则将 $\textit{cnt}$ 重置为 0。然后判断 $\textit{cnt}$ 是否大于等于 $\textit{k}$ 即可。

时间复杂度 $O(1)$ ，空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class DataStream:
    def __init__(self, value: int, k: int):
        self.val, self.k = value, k
        self.cnt = 0

    def consec(self, num: int) -> bool:
        self.cnt = 0 if num != self.val else self.cnt + 1
        return self.cnt >= self.k


# Your DataStream object will be instantiated and called as such:
# obj = DataStream(value, k)
# param_1 = obj.consec(num)

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Looking for efficient use of data structures to maintain state in a dynamic stream.
question_mark
Testing knowledge of sliding window techniques and queue management.
question_mark
Evaluating how the candidate manages performance under constraints.

warning

常见陷阱

外企场景

error
Failing to handle stream updates correctly when the queue size exceeds k.
error
Not maintaining constant time checks for `consec()` or using inefficient data structures.
error
Overcomplicating the solution by introducing unnecessary logic or data structures.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Modify the solution to handle multiple different values to check for in the stream.
arrow_right_alt
Adapt the solution to track consecutive increasing or decreasing sequences of integers.
arrow_right_alt
Change the constraints to allow for larger values of k and test performance at scale.

help

常见问题

外企场景

继续练习

#2034 股票价格波动 #2013 检测正方形 #1825 求出 MK 平均值