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.
    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.

分析

实现一个最小栈,可以以常数时间获取栈中的最小元素

代码

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
39
40
class MinStack(object):
def __init__(self):
self.q = []
# @param x, an integer
# @return an integer
def push(self, x):
curMin = self.getMin()
if curMin == None or x < curMin:
curMin = x
self.q.append((x, curMin));
# @return nothing
def pop(self):
self.q.pop()
# @return an integer
def top(self):
if len(self.q) == 0:
return None
else:
return self.q[len(self.q) - 1][0]
# @return an integer
def getMin(self):
if len(self.q) == 0:
return None
else:
return self.q[len(self.q) - 1][1]
# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(x)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()

点评

典型的用空间换时间做法,要想快速获取最小元素,就需要牺牲空间,做一些额外的存储。
这里的巧妙之处在于不使用两个栈,而是直接将一个复合数据存到一个栈里的一个层次里。存储原始值的同时,也存储该层作为栈顶时当前栈的最小值
注意分析时间复杂度 可不可以牺牲空间,让 pop 和 push 都是 常数时间呢?好像没有??