3.5 归纳总结与思维拓展

教材导航 · 第3章

原书定位

印刷页P108起,对应PDF第120页。下文为目视整理的知识提要;完整内容见原书对照。

栈和队列可以作为算法工具,题目允许时直接调用其基本操作即可;仍须清楚空满检查、指针变化与辅助空间。

最小栈可用同步辅助栈实现:主栈每次入栈 xx,辅助栈压入“此前最小值与 xx 中较小者”;两个栈同步出栈,辅助栈顶就是当前最小值。入栈、出栈、查询最小值均为 O(1)O(1),额外空间 O(n)O(n)。

关联知识

原书对照

展开原书对照截图

原书对照,原书P108,PDF第120页