包含min函数的栈

定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。

考虑申请一个辅助栈来存储栈中最小的值，这样就可以以O（1）时间复杂度，返回直接返回。

import java.util.Stack; public class Solution { Stack<Integer> stack = new Stack<>(); Stack<Integer> min = new Stack<>(); public void push(int node) { stack.push(node); min.push(min.isEmpty()?node:Math.min(node,min.peek())); } public void pop() { stack.pop(); min.pop(); } public int top() { return stack.top(); } public int min() { return min.top(); } }

为了解决内存占用过高的问题，可以只在辅助栈中压入较小的数据。

import java.util.Stack; public class Solution { Stack<Integer> stack = new Stack<>(); Stack<Integer> min = new Stack<>(); public void push(int node) { stack.push(node); //min.push(min.isEmpty()?node:Math.min(node,min.peek())); if(min.isEmpty()){ min.push(node); } else{ if(node <= min.peek()) min.push(node); } } public void pop() { if(stack.peek() == min.peek()){ min.pop(); } stack.pop(); } public int top() { return stack.peek(); } public int min() { return min.peek(); } }