剑指offer29 JZ30 包含min函数的栈
包含min函数的栈
https://www.nowcoder.com/practice/4c776177d2c04c2494f2555c9fcc1e49?tpId=13&tqId=23268&ru=%2Fpractice%2F54275ddae22f475981afa2244dd448c6&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&sourceUrl=%2Fexam%2Foj%2Fta%3Fpage%3D1%26tpId%3D13%26type%3D13
思路
- 首先初始化原始栈stack 和最小值栈stack_min(存储每次跟原栈中元素比较后的最小元素):
- 接下来插入(push) ‘1’这个元素,此时两个栈的变化如下图:
- 然后再插入(push) ‘2’这个元素,此时两个栈又变化如下图:
- 接着要获取栈顶元素,如下图:
- 而弹出栈顶元素,也直接调用pop函数 即可。
- 接着再次插入第三个元素 ‘1’,两个栈又发生如下变化👇:
![alt]
- 最后再次利用top函数获取到栈顶元素就变成了 1,调用min函数则获取最小值依然是 -1。
代码
import java.util.Stack;
public class Solution {
Stack<Integer> stack=new Stack<Integer>();
//用来存贮最小元素的最小栈
Stack<Integer> stack_min=new Stack<Integer>();
public void push(int node) {
//普通栈直接放
stack.push(node);
//最小栈需要对比之后在放入
//为空放入第一个元素
if(stack_min.isEmpty()){
stack_min.push(node);
}
//值比最小栈顶部元素小 直接放入最小栈
else if(node<=stack_min.peek()){
stack_min.push(node);
}//值大放入自身顶部元素
else{
stack_min.push(stack_min.peek());
}
}
public void pop() {
stack.pop();
stack_min.pop();
}
public int top() {
// 可以不加
// stack_min.peek();
return stack.peek();
}
public int min() {
return stack_min.peek();
}
}