约 8 分钟
势能法给数据结构定义一个“势能”,慢操作释放势能、快操作积累势能,用势能变化把峰值代价摊平。直觉是:用平时存下的余量抵消偶发的昂贵操作。单调栈、并查集分析常用它。
单调栈里每个元素最多被 push、pop 各一次,这体现了什么分析?
登录 后可看答案