1. 题目描述
定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。
注意：保证测试中不会当栈为空的时候，对栈调用pop()或者min()或者top()方法。
2. 题目分析
该题有二种解决方法
2.1 常规解决思路：
在写min()方法的时候，建立一个辅助栈，将stack中的元素导入至辅助栈中，并且比较出来最小值，在从辅助栈导入至stack中。
2.2 剑指offer思路：
创建两个栈，分别为数据栈（stcak1）和辅助栈（stack2），每一次数据（node）储存至数据栈时，判断当前的辅助栈是否为空和node是否小于辅助栈中最小的数值（也就是栈顶的数值）。若小于，则将node压入辅助栈（作为最小值）。若大于，则将辅助栈顶的数字再一次压入。
3. 题目代码
常规思路代码
import java.util.Stack; public class Solution { Stack<Integer> stack = new Stack<Integer>(); Stack<Integer> stack1 = new Stack<Integer>(); public void push(int node) { stack.push(node); } public void pop() { stack.pop(); } public int top() { return stack.peek(); } public int min() { int min = stack.peek(); while (stack.isEmpty() != true) { int node = stack.pop(); if (node < min) { min = node; } stack1.push(node); } while (stack1.isEmpty() != true) { stack.push(stack1.pop()); } return min; } }
剑指offer思路
Stack<Integer> stack1 = new Stack<Integer>(); Stack<Integer> stack2 = new Stack<Integer>(); public void push(int node) { stack1.push(node);//将数据保存至数据栈 //当辅助栈为空或者当前数据小于辅助栈中最小的值时 添加至辅助栈 if(stack2.isEmpty() || node < stack2.peek()) { stack2.push(node); }else { stack2.push(stack2.peek()); } } public void pop() { stack1.pop(); stack2.pop(); } public int top() { return stack1.peek(); } public int min() { return stack2.peek(); }
