Leetcode-155 Min Stack

发表于 | 分类于 | 次

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.

Example 1

1
2
3
4
5
6
7
8
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> Returns -3.
minStack.pop();
minStack.top();      --> Returns 0.
minStack.getMin();   --> Returns -2.

解题思路

在常数时间内获取栈中最小值，需要维护一个 minv 变量，用于保存当前栈的最小值。pop 一个元素时，若该元素等于 minv，需要更新 minv。若要在常数时间更新 minv，需要保存 push(x=minv) 之前栈的最小值，可以在 push(x=minv) 之前先 push 旧的 minv。这样，在 pop(x=minv) 时，可以利用旧的 minv 更新 minv。

复杂度分析

  • 时间复杂度：$O(1)$
  • 空间复杂度：$O(n)$

代码

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
27
28
29
30
31
32
33
34
35
36
37
38
class MinStack {
	vector<int> data;
	int minv = INT_MAX;
public:
	/** initialize your data structure here. */
	MinStack() {}

	void push(int x) {
		if (x <= minv) {
			data.push_back(minv);
			data.push_back(x);
			minv = x;
		}
		else data.push_back(x);
	}

	void pop() {
		if (!data.empty()) {
			if (data.back() == minv) {
				data.pop_back();
				minv = data.back();
				data.pop_back();
			}
			else data.pop_back();
		}
	}

	int top() {
		if (!data.empty()) {
			return data.back();
		}
		return minv;
	}

	int getMin() {
		return minv;
	}
};