考察点:用空间换时间的设计思维——辅助栈与主栈的同步关系。追问:只用一个变量记录最小值,pop 之后会出什么问题?
要点:配一个同步维护的辅助栈,栈顶永远保存「当前主栈全部元素的最小值」。
- 主栈正常存数据;
- 辅助栈在 push 时压入 min(x, 辅助栈栈顶)(辅助栈为空时直接压 x);pop 时两栈同时弹出。
x <= 当前最小值 时压栈、pop 时 主栈顶 == 辅助栈顶 才同步弹出,可减少重复元素;或用「差值编码」把辅助栈存成 x - prevMin,进一步省空间。题目与答案就在本页;收藏、批注和错题重练在应用内