定义栈的数据结构,请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中,调用 min、push 及 pop 的时间复杂度都是 O(1)。
示例:
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.min(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.min(); --> 返回 -2.
提示:
各函数的调用总次数不超过 20000 次
作者:Krahets
链接:https://leetcode.cn/leetbook/read/illustration-of-algorithm/50bp33/
来源:力扣(LeetCode)
思路:
难点:降低获取栈中最小元素的时间复杂度
方法:维护一个最小值栈
元素栈每入栈一个元素
如果其比当前最小栈栈顶元素小或者栈空
将其加入到最小栈中,按照此种思想生成非严格降序的子序列
并且最小栈的栈顶元素为元素栈中的最小元素
当弹栈 时,如果当前元素等于最小栈栈顶元素 那么俩个栈同时弹栈
调用min时直接返回最小栈 栈顶元素
标签:元素,minStack,Offer,30,最小,min,栈中,push From: https://www.cnblogs.com/TrenmenHu/p/16659356.html