TikTok 登录登出人数峰值：差分与平台规则

题意与假设

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

• 训练整数秒、半开[login,logout)，计会话数而非distinct uid。
• 输出当天内部严格单秒峰，平台不是峰，端点不算；实际题的时间粒度/平台政策缺失，保留待核。

解题路线

1. 每区间start加1、end减1，对差分做前缀得到每秒在线会话数；同秒入/出合并，自然符合半开语义。
2. 检查count[t]>count[t-1]且>count[t+1]，不能只找全日最大，也不能只看某事件后上涨。
3. 若要平台峰，压成最大相同人数区间，再比较左右较低邻段；输出起止或代表点须确认，不能和严格单点混用。
4. 时间域很大可排序事件生成常值segments，节约秒级数组，但仍需按目标峰定义推理；不同uid重叠会话要先做每用户合并才是distinct用户数。

手动走一遍

会话[1,2)、[1,3)形成人数0,2,1，秒1为严格峰；[1,3)一条会话形成0,1,1,0，按本文不是峰。logout恰为一天终点允许，但该秒不属于当天数组。

Python 参考实现

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

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

def online_local_maxima(records, day_seconds):
    """Training: integer second timestamps, half-open [login,logout).
    Count sessions, not distinct users; output strict interior second peaks.
    Endpoints are excluded; plateaus are not peaks. Zero-length sessions ignored."""
    if day_seconds < 1:
        raise ValueError('positive day length required')
    difference=[0]*(day_seconds+1)
    for user,start,end in records:
        if not (0<=start<=end<=day_seconds):
            raise ValueError('invalid interval')
        difference[start]+=1;difference[end]-=1
    counts=[];current=0
    for second in range(day_seconds):
        current+=difference[second];counts.append(current)
    return [(s,counts[s]) for s in range(1,day_seconds-1)
            if counts[s]>counts[s-1] and counts[s]>counts[s+1]]

复杂度

N会话、S秒，差分 O(N+S)时间、O(S)空间；事件版 O(N log N)时间、O(N)空间，避免过大时间跨度。

易错点与追问

容易失分的边界

• 把全局最大当局部峰。
• 平台返回任意点却没约规则。
• 重复会话当唯一用户。

继续深挖

• 如何输出峰平台区间？
• 按distinct uid计数怎样处理重叠？