1.题目描述
定义栈的数据结构,请在该类型中实现一个能够得到栈中所含最小元素的min函数(时间复杂度应为O(1))。
2.解题思路
解题思路:利用辅助栈来存储现有栈的最小值。在入栈和出栈的时候将现有栈和最小值栈进行比较。
(1)入栈时,若新值比最小值栈的栈顶还小,则将该值同时push到最小值栈; (2)出栈时,若现有栈的栈顶和最小值栈栈顶一致,则同时出栈,
(3)否则,仅仅现有栈pop;通过这一操作,最小值栈的栈顶将永远是现有栈元素中的最小值。
3.代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54
| public class Solution { Stack<Integer> data_stack =new Stack<>();
Stack<Integer> min_stack = new Stack<>(); public void push(int node) {
if(min_stack.isEmpty()||min_stack.peek()>=node){
min_stack.push(node); }else {
min_stack.push(min_stack.peek()); }
data_stack.push(node); } public void pop() { if(data_stack.empty()||min_stack.empty()) { return; }
data_stack.pop();
min_stack.pop(); }
public int top() { if(!data_stack.isEmpty()) { return data_stack.peek(); } return 0; }
public int min() { if(!min_stack.empty()) { return min_stack.peek(); } return 0; } }
|
补充
stack.peek:获取栈顶元素,返回栈顶元素但是不移除它
stack.add:向栈中添加元素,成功返回true
stack.push:向栈中添加元素,返回结果是当前添加的元素
stack.pop:移除并返回栈顶元素
stack.isEmpty:检查是否为空栈
stack.search(“value”):查看某元素再栈中的位置,计算从1开始