# 定义栈的数据结构,请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中,调用 min、push 及 pop 的时间复杂度都是 O(1)。 示例: MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.min(); --> 返回 -3. minStack.pop(); minStack.top(); --> 返回 0. minStack.min(); --> 返回 -2. 提示: 1.各函数的调用总次数不超过 20000 次
题目解读:
- 获取栈的最小值min()需要遍历整个栈,复杂度为O(n),需要将min()函数的复杂度降为O(1)。
解题思路:
- 辅助栈:
-
栈stack1存储所有元素
-
栈stack2存储stack1中所有非严格递减的元素
- push()函数:保证填充stack1,及填充栈stack2非严格递减元素
- pop()函数:当stack1与stack2顶部值相同时,同时d出。保证stack1与stack2元素的一致性
- top()函数返回stack1的顶部元素
- min()函数返回最小值
Java代码:
import java.util.Stack; public class MinStack { Stackstack1,stack2; // 初识化 public MinStack(){ stack1 = new Stack (); stack2 = new Stack (); } public void push(int x){ stack1.push(x); if(stack2.isEmpty() || stack2.peek()>=x){ stack2.push(x); } } //d出stack1与stack2的最小值 保持两栈元素的一致性 public void pop(){ if(stack1.pop().equals(stack2.peek())){ stack2.pop(); } } // 返回栈stack1的顶部元素 public int top(){ return stack1.peek(); } // 返回栈的最小值 public int min(){ return stack2.pop(); } // 测试 public static void main(String[] args) { MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); System.out.println(minStack.min()); minStack.pop(); System.out.println( minStack.top()); System.out.println(minStack.min()); } }
Java 代码中,由于 Stack 中存储的是 int 的包装类 Integer ,因此需要使用 equals() 代替 == 来比较值是否相等。
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)