LeetCode Min Stack

LeetCode 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:

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.

本题要实现一个最小栈,使得push, pop, top以及getMin都是以O(1)的时间完成。

这是一个非常经典的双栈法题目,我居然不知道。同时使用两个栈,一个普通的用于存放所有数据allStack,另一个只用于存储最小值序列minStack。

push的时候,每次都把x push进allStack。如果minStack为空,则是第一次push,要把x push进minStack;如果minStack非空,则当x小于等于minStack栈顶时,可以把x push进minStack。注意当x等于minStack栈顶的时候也是需要进栈的,因为有可能有重复元素,比如对0,1,0依次进栈,遇到后面的0时,minStack只有前一个0,此时如果后一个0不进栈,如果下一步是pop的话,就会把minStack中的上一个0 pop掉,那么此时getMin时就会出错,因为此时minStack里没东西了,但allStack还保留着0和1,正确的最小值应该是前一个0。

pop时,allStack正常pop。如果pop出来的值等于minStack的栈顶,则minStack也需要pop。

top就取allStack的top。

getMin就取minStack的top。

完整代码如下:

class MinStack {
private:
	stack<int> allStack, minStack;

public:
	/** initialize your data structure here. */
	MinStack() {

	}

	void push(int x) {
		if (minStack.empty()) {
			minStack.push(x);
		}
		else if (x <= minStack.top()) { // 注意是<=而不是<
			minStack.push(x);
		}
		allStack.push(x);
	}

	void pop() {
		int top = allStack.top();
		allStack.pop();
		if (top == minStack.top()) {
			minStack.pop();
		}
	}

	int top() {
		return allStack.top();
	}

	int getMin() {
		return minStack.top();
	}
};

本代码提交AC,用时29MS。

二刷。其实可以更简单一点,辅助的minStack大小始终和allStack一样,当新入元素小于minStack栈顶元素时,自然入minStack;否则,就把minStack栈顶的元素再入一次栈。这样就使得两个栈的大小一样,pop的时候可以同时pop,减少了各种if判断。

完整代码如下:

class MinStack {
private:
	stack<int> allStack, minStack;

public:
	/** initialize your data structure here. */
	MinStack() {
	}

	void push(int x) {
		if (minStack.empty() || x < minStack.top()) {
			minStack.push(x);
		} else {
			minStack.push(minStack.top());
		}
		allStack.push(x);
	}

	void pop() {
		allStack.pop();
		minStack.pop();
	}

	int top() {
		return allStack.top();
	}

	int getMin() {
		return minStack.top();
	}
};

本代码提交AC,用时29MS。

Leave a Reply

Your email address will not be published. Required fields are marked *