栈

第二次碰到这道题了，又学了两种解题方法，记录一下。 题目介绍 设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。 实现 MinStack 类: MinStack() 初始化堆栈对象。 void push(int val) 将元素val推入堆栈。 void pop() 删除堆栈顶部的元素。 int top() 获取堆栈顶部的元素。 int getMin() 获取堆栈中的最小元素。 解法一：使用辅助栈 这个也是最简单的，题目没有空间限制，考虑使用两个栈，主栈正常记录元素进出，辅助栈记录每个元素对应最小值的进出，辅助栈的栈顶保持为主栈所有元素的最小值。 当元素入栈时，比较该元素和辅助栈的栈顶，如果该元素更小，那么将其推入主栈的同时也将其推入辅助栈。 当元素出栈时，如果主栈栈顶元素值和辅助栈的栈顶元素值相等。那么将该元素从两个栈里同时弹出，否则正常弹出主栈栈顶元素。 class MinStack { Deque<Integer> stack1; Deque<Integer> stack2; public MinStack() { stack1 = new ArrayDeque<>(); stack2 = new ArrayDeque<>(); } public void push(int val) { stack1.push(val); if (stack2.isEmpty() || val <= stack2.peek()) { stack2.push(val); } } public void pop() { int num = stack1.pop(); if (num == stack2.peek()) stack2.pop(); } public int top() { return stack1.peek(); } public int getMin() { return stack2.peek(); } } 解法二：使用自定义链表 评论区有评论说面试官要求使用栈以外的数据结构来设计，所以找到这种方法。 ...