Leetcode 155 - Min Stack

DocumentsAlgorithms
Algorithms, Leetcode, Python
Catalogue
  1. 1. Question
  2. 2. Explanation
  3. 3. Code

Question

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.

Explanation

Using an addition list to the minimum value every time the stack is updated. Therefore, getMin() will not take O(n) time complexity. Appending the new value to the end of the list will reduce the complexity of changing the stack.

Code

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
class MinStack(object):

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.stack = []
        self.min = []

    def push(self, x):
        """
        :type x: int
        :rtype: void
        """
        self.stack.append(x)
        if not self.min or self.min[-1] > x:
            self.min.append(x)
        else:
            self.min.append(self.min[-1])

    def pop(self):
        """
        :rtype: void
        """
        self.stack.pop()
        self.min.pop()
        
        
    def top(self):
        """
        :rtype: int
        """
        return(self.stack[-1])

    def getMin(self):
        """
        :rtype: int
        """
        return self.min[-1]
Comments