题目:定义栈的数据结构,请在该类型中实现一个能够找得到栈的最小元素的min函数。在该栈中,调用min,push以及pop的时间复杂度都是O(1)
思路:如果每次都把最小元素压入辅助栈,就能保证辅助栈的栈顶一直都是最小元素。当最小元素从数据栈内被弹出来之后,同时弹出辅助栈的栈顶元素,此时辅助栈的新栈顶元素就是下一个最小值。
![](https://img.haomeiwen.com/i7818674/dd75235b8fbe704e.png)
![](https://img.haomeiwen.com/i7818674/8e1639e2ebb916ea.png)
题目:定义栈的数据结构,请在该类型中实现一个能够找得到栈的最小元素的min函数。在该栈中,调用min,push以及pop的时间复杂度都是O(1)
思路:如果每次都把最小元素压入辅助栈,就能保证辅助栈的栈顶一直都是最小元素。当最小元素从数据栈内被弹出来之后,同时弹出辅助栈的栈顶元素,此时辅助栈的新栈顶元素就是下一个最小值。
本文标题:面试题21:包含min函数的栈
本文链接:https://www.haomeiwen.com/subject/zmocvxtx.html
网友评论