FilesExpand file tree

 master

/

min-stack.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

83 lines (72 loc) · 2 KB

 master

/

min-stack.py

Copy path

Top

File metadata and controls

• Code
• Blame

83 lines (72 loc) · 2 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

# Time: O(n)

# Space: O(1)

#

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

#

class MinStack:

def __init__(self):

self.min = None

self.stack = []

# @param x, an integer

# @return an integer

def push(self, x):

if not self.stack:

self.stack.append(0)

self.min = x

else:

self.stack.append(x - self.min)

if x < self.min:

self.min = x

# @return nothing

def pop(self):

x = self.stack.pop()

if x < 0:

self.min = self.min - x

# @return an integer

def top(self):

x = self.stack[-1]

if x > 0:

return x + self.min

else:

return self.min

# @return an integer

def getMin(self):

return self.min

# Time: O(n)

# Space: O(n)

class MinStack2:

def __init__(self):

self.stack, self.minStack = [], []

# @param x, an integer

# @return an integer

def push(self, x):

self.stack.append(x)

if len(self.minStack):

if x < self.minStack[-1][0]:

self.minStack.append([x, 1])

elif x == self.minStack[-1][0]:

self.minStack[-1][1] += 1

else:

self.minStack.append([x, 1])

# @return nothing

def pop(self):

x = self.stack.pop()

if x == self.minStack[-1][0]:

self.minStack[-1][1] -= 1

if self.minStack[-1][1] == 0:

self.minStack.pop()

# @return an integer

def top(self):

return self.stack[-1]

# @return an integer

def getMin(self):

return self.minStack[-1][0]

if __name__ == "__main__":

stack = MinStack()

stack.push(-1)

print [stack.top(), stack.getMin()]