[LeetCode] 0155. Min Stack 最小栈 & C++Runtime加速

题目

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 推入栈中。
  • pop() – 删除栈顶的元素。
  • top() – 获取栈顶元素。
  • getMin() – 检索栈中的最小元素。

Example:

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.

解法一

用两个栈就完事了,值得一说的是加速代码,暂时没找到什么空间复杂度很低的算法。

参考资料:https://blog.csdn.net/yujuan_mao/article/details/8119529

取消标准输入输出的同步,可以加速输入三倍(因为cin太慢啦),关掉cin和stdin的同步后,再把cin和cout的绑定也取消掉。瞬间提速……

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
static int x = [](){
std::ios::sync_with_stdio(false);
std::cin.tie(NULL);
std::cout.tie(NULL);
return NULL;
}();

class MinStack {
private:
stack<int> data;
stack<int> min_stack;
public:
/** initialize your data structure here. */
MinStack() = default;

void push(int x) {
data.push(x);
if (min_stack.empty() || min_stack.top() >= x) {
min_stack.push(x);
}
}

void pop() {
if (data.top() == min_stack.top()) {
min_stack.pop();
}
data.pop();
}

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

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

运行结果

1
2
Runtime: 28 ms, faster than 98.82% of C++ online submissions for Min Stack.
Memory Usage: 17.2 MB, less than 12.90% of C++ online submissions for Min Stack.