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^9
  • 1 <= k <= 10^5
  • 最多调用 consec 10^5 次

解题思路

这道题需要维护一个数据流，并检查最后 k 个元素是否都等于目标值。有两种主要的解题思路：

方法一：队列维护（直观但空间复杂度较高） 使用队列存储最后 k 个元素，每次添加新元素时维护队列大小为 k，然后检查队列中所有元素是否都等于目标值。

方法二：计数器优化（推荐） 关键观察：我们只需要知道最后 k 个元素中有多少个等于目标值。可以维护一个计数器，记录当前连续出现目标值的次数。当遇到非目标值时，计数器重置为 0；当遇到目标值时，计数器加 1（但不超过 k）。只有当计数器达到 k 时才返回 true。

这种方法避免了存储具体的元素，只需要 O(1) 的空间复杂度，同时每次操作也是 O(1) 时间复杂度。核心思想是：如果最后 k 个元素都等于目标值，那么必然是连续的 k 个目标值，所以只需要追踪连续计数即可。

代码实现

class DataStream {
private:
    int targetValue;
    int k;
    int consecutiveCount;
    
public:
    DataStream(int value, int k) : targetValue(value), k(k), consecutiveCount(0) {
    }
    
    bool consec(int num) {
        if (num == targetValue) {
            consecutiveCount++;
        } else {
            consecutiveCount = 0;
        }
        
        return consecutiveCount >= k;
    }
};

class DataStream:
    def __init__(self, value: int, k: int):
        self.target_value = value
        self.k = k
        self.consecutive_count = 0

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

public class DataStream {
    private int targetValue;
    private int k;
    private int consecutiveCount;

    public DataStream(int value, int k) {
        this.targetValue = value;
        this.k = k;
        this.consecutiveCount = 0;
    }
    
    public bool Consec(int num) {
        if (num == targetValue) {
            consecutiveCount++;
        } else {
            consecutiveCount = 0;
        }
        
        return consecutiveCount >= k;
    }
}

var DataStream = function(value, k) {
    this.value = value;
    this.k = k;
    this.count = 0;
};

DataStream.prototype.consec = function(num) {
    if (num === this.value) {
        this.count++;
    } else {
        this.count = 0;
    }
    return this.count >= this.k;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

操作时间复杂度空间复杂度
DataStream()O(1)O(1)
consec()O(1)O(1)
总体O(n)O(1)

其中 n 是 consec 方法的调用次数。

相关题目