动态集合是指大小不固定的集合,会增加新的元素和删除已有的元素。 队列,堆栈,树,vector ,map 等都属于动态集合。
实现主要就是2种方向:
1)基于node的
一维的就是链表,二维的就是二叉树
2)基于数组的
当数组被填满或大于一定的factor的时候,重新申请一片大的连续存储区,然后copy之前的元素。
动态Order Statistic 系统(动态ranking 系统)
红黑树 + 节点存储树的大小信息
rank(node) = node->left->size +1
能O(1) 访问Min的 堆栈
引入一个辅助栈 minStack,维护最小值历史。如果新push的值小于等于minStack顶,则同时push到minStack。如果pop的value等于minStack顶,同时pop minStack。这里注意push的时候,等于minStack栈顶也要push 到minStack,因为相同最小值可能有多个,不能只用一个表示。
能O(1)访问Min的队列
队列和栈不同,直接用栈的方式有问题。正确的方法是,结合 ”用两个栈实现队列“ 和”能O(1)访问Min的栈“,先实现一个能O(1)访问Min的栈,再用两个这样的栈实现队列,队列的min 为 min( stack1.min(), stack2.min())。