题目描述 定义栈的数据结构，请在该类型中实现一个能够得到栈最小元素的min函数。

方法一：

只有一个栈空间，节省空间，但是min方法的时间复杂度是O(n)

import java.util.Stack; public class Solution { private Stack<Integer> stack = new Stack<>(); public void push(int node) { stack.push(node); } public void pop() { stack.pop(); } public int top() { return stack.peek(); } public int min() { if(stack.empty()) { throw new RuntimeException("The stack is already empty"); } int min = top(); for(int a : stack) { if(a < min) { min = a; } } return min; } }

---

方法二：

思路： 把每次的最小元素（之前的最小元素和新压入战的元素两者的较小值）都保存起来放到另外一个辅助栈里。 如果每次都把最小元素压入辅助栈， 那么就能保证辅助栈的栈顶一直都是最小元素．当最小元素从数据栈内被弹出之后，同时弹出辅助栈的栈顶元素，此时辅助栈的新栈顶元素就是下一个最小值。

import java.util.Stack; public class Solution { // 数据栈，用于存放插入的数据 private Stack<Integer> dataStack = new Stack<>(); // 最小数位置栈，存放数据栈中最小的数的位置 private Stack<Integer> minStack = new Stack<>(); public void push(int node) { dataStack.push(node); if(dataStack.size() == 1) { minStack.push(0); } else { if(node < dataStack.get(minStack.peek())) { minStack.push(dataStack.size() - 1); } else { minStack.push(minStack.peek()); } } } public void pop() { if (dataStack.isEmpty()) { throw new RuntimeException("The stack is already empty"); } dataStack.pop(); minStack.pop(); } public int top() { if (dataStack.isEmpty()) { throw new RuntimeException("The stack is already empty"); } minStack.pop(); return dataStack.pop(); } public int min() { if (dataStack.isEmpty()) { throw new RuntimeException("The stack is already empty"); } return dataStack.get(minStack.peek()); } }

---

涉及的知识点：

Stack