势能直觉

8 分钟

势能法给数据结构定义一个“势能”,慢操作释放势能、快操作积累势能,用势能变化把峰值代价摊平。直觉是:用平时存下的余量抵消偶发的昂贵操作。单调栈、并查集分析常用它。

小纸条

单调栈里每个元素最多被 push、pop 各一次,这体现了什么分析?

登录 后可看答案

势能直觉 · 算法进阶 · op599 课程