Min Stack Problem


Description

LeetCode Problem 155.

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

Implement the MinStack class:

  • MinStack() initializes the stack object.
  • void push(int val) pushes the element val onto the stack.
  • void pop() removes the element on the top of the stack.
  • int top() gets the top element of the stack.
  • int getMin() retrieves the minimum element in the stack.

Example 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Input
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]
Output
[null,null,null,null,-3,null,0,-2]
Explanation
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); // return -3
minStack.pop();
minStack.top();    // return 0
minStack.getMin(); // return -2

Constraints:

  • -2^31 <= val <= 2^31 - 1
  • Methods pop, top and getMin operations will always be called on non-empty stacks.
  • At most 3 * 10^4 calls will be made to push, pop, top, and getMin.


Sample C++ 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
class MinStack {
public:
    stack<int> st;
    stack<int> minst;
    
    MinStack() {
        
    }
    
    void push(int x) {
        st.push(x);
        int y;
        if (!minst.empty()) {
            y = minst.top();
            minst.push(min(x, y));
        } else {
            minst.push(x);
        }
    }
    
    void pop() {
        st.pop();
        minst.pop();
    }
    
    int top() {
        if (st.empty())
            return 0;
        return st.top();
    }
    
    int getMin() {
        if (minst.empty())
            return 0;
        return minst.top();
    }
};




Related Posts

Validate Stack Sequences Problem

LeetCode 946. Given two integer arrays pushed and popped each...

Stamping The Sequence Problem

LeetCode 936. You are given two strings stamp and target....

Score Of Parentheses Problem

LeetCode 856. Given a balanced parentheses string s, return the...

Minimum Add To Make Parentheses Valid Problem

LeetCode 921. A parentheses string is valid if and only...

Maximum Width Ramp Problem

LeetCode 962. A ramp in an integer array nums is...

Decoded String At Index Problem

LeetCode 880. You are given an encoded string s. To...