导航
导航
文章目录
  1. 题目
  2. 翻译

LeetCode-155.Min Stack

题目

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

  • push(x) – Push element x onto stack.
  • pop() – Removes the element on top of the stack.
  • top() – Get the top element.
  • getMin() – Retrieve the minimum element in the stack.

翻译

设计一个栈,支持push、pop、top操作,并能在常数时间内取出最小元素。

  • push(x) – 将元素x push到栈顶部。
  • pop() – 将元素从栈顶移除。
  • top() – 获取顶部元素。
  • getMin() – 取出栈中最小的元素。

另外设立一个栈,记录当前最小值。
push操作时,若最小值栈为空,则进栈;若不为空,与栈顶元素比较,如果小于栈顶元素,进栈,否则不操作;
pop操作时,与最小值栈栈顶元素比较,若相等则最小值栈也pop;若大于则不操作(不可能小于);
top操作时,直接返回栈顶元素;
getMin操作时,直接返回最小栈栈顶元素:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class MinStack {
Stack<Integer> minStack, minValues;

public MinStack() {
minStack = new Stack<Integer>();
minValues = new Stack<Integer>();
}

public void push(int x) {
minStack.push(x);
if (minValues.isEmpty() || minValues.peek() >= x) minValues.push(x);
}

public void pop() {
if (minStack.peek().equals(minValues.peek())) minValues.pop();
minStack.pop();
}

public int top() {
return minStack.peek();
}

public int getMin() {
return minValues.peek();
}
}