找到数据流中的连续整数

难度: Medium

给你一个整数数据流，请你实现一个数据结构，检查数据流中最后 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⁵ 次。

Submission

运行时间: 304 ms

内存: 46.7 MB

class DataStream:

    def __init__(self, value: int, k: int):
        self.target, self.cnt, self.k = value, 0, k

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



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

Explain

此题解采用的是一种计数方法来检查数据流中最后 k 个整数是否等于初始化时指定的 value。在构造函数中，初始化 value 和 k 的值，并设置一个计数器 cnt 用于记录连续等于 value 的整数数量。在 consec 方法中，每次调用时都会将传入的整数 num 与 value 进行比较。如果 num 等于 value，则增加计数器 cnt；否则，重置计数器 cnt 为 0。最后，如果 cnt 的值大于等于 k，则返回 true 表示最后 k 个整数都等于 value，否则返回 false。

时间复杂度: O(1)

空间复杂度: O(1)

class DataStream:

    def __init__(self, value: int, k: int):
        self.value = value  # 要检查的目标值
        self.k = k          # 需要连续匹配的整数数量
        self.cnt = 0        # 当前连续匹配的计数

    def consec(self, num: int) -> bool:
        # 如果 num 是目标值，则计数器增加，否则重置计数器
        self.cnt = 0 if num != self.value else self.cnt + 1
        # 如果计数器达到或超过 k，则返回 true，否则返回 false
        return self.cnt >= self.k

Explore

在DataStream类中，`value`和`k`被定义为实例变量，这是因为它们对于对象的整个生命周期都是必要的，并且在多次调用`consec`方法时保持不变。将这些参数作为实例变量存储，避免了每次调用方法时重复传递相同的参数，从而简化了方法的调用，并且使得类的设计更加符合面向对象的封装性原则。

`cnt`变量在DataStream类中用于记录连续出现目标值`value`的次数。当新加入的数字等于`value`时，`cnt`递增；若不等，则`cnt`重置为0。这样的机制确保了只有当最近连续的数字全部等于`value`时，`cnt`的值才会达到或超过`k`。但实际上，`cnt`并不直接限制只计算最后k个数，而是连续计数，如果连续数字超过k个，`cnt`也会继续增长。

如果数据流中的数字数量少于k个，由于`cnt`只在连续出现目标值时增加，且必须连续出现`value`才会导致`cnt`达到k，因此在数据流中的数字数量少于k个的情况下，`cnt`值不可能达到k。在这种情况下，`consec`方法将始终返回false，因为还没有足够的数字来满足连续k个数等于`value`的条件。

在`DataStream`类的实现中，如果在达到或超过k个连续数字等于`value`之后，再次添加一个不等于`value`的数字，`cnt`将被立即重置为0。这是因为`cnt`的设计是用来跟踪当前连续的等于`value`的数字数量，一旦遇到一个不等的值，之前的连续计数失效，需要重新开始计数。