寻找搜索连续最小值时避免频繁push/pop的data structure及online algorithm

筛选目标为保留数据流的严格递增后缀极小值点，结合数据流整体呈递增趋势、留存率极低（约3e-6）的特性，可通过以下方案解决普通单调栈高频push/pop的性能问题：

方案1：块缓存批处理方案（落地成本最低，性能提升最明显） #

核心思路是把高频单次操作转为低频批量操作，利用极低留存率的特性减少栈交互次数

• 先设置固定大小的内存块缓存（可配置为32MB/64MB，远小于最终留存阈值即可），数据流先写入缓存块，不直接操作栈
• 缓存块写满后，先对整块做离线极小值点预筛选：从后往前遍历缓存块，仅保留块内满足「小于块内后续所有值」的点，这一步可筛掉块内99.99%以上的数据
• 将预筛选得到的少量点按顺序输入普通单调栈做全局校验，此时每个缓存块仅需操作个位数的点，完全避免了原方案单条数据就触发栈操作的问题
• 性能收益：原方案每TB数据需做万亿次量级的栈操作，优化后仅需数千次，性能提升至少6个数量级

方案2：边界预判剪枝方案（适配极高速数据流场景） #

利用数据流整体递增的特性做预判，进一步减少不必要的计算

• 记录当前栈顶的数值为current_min，因数据流整体递增，99.9%以上的新数据都会大于current_min，可直接丢弃，不需要进入缓存也不需要任何后续计算
• 仅当遇到小于current_min的异常值时，才触发缓存写入和后续的批处理逻辑
• 若数据流的递增趋势非严格、存在偶发回落，仅需把边界阈值调整为current_min * 容错系数即可，系数根据数据波动幅度设置

额外工程优化点 #

• 栈存储可直接用预分配的数组实现，不需要用链表结构的栈，push/pop都直接操作数组下标，性能更高
• 多线程场景下可把不同分片的数据流先做独立的块筛选，再合并结果，进一步提升吞吐

内容的提问来源于stack exchange，提问作者Charles