Post
Ask Question

Min Stack

I came from science, I have never had a chance to learn or play a game such as an algorithm in my student career. Most algorithm problems I met are in interviews. In my view, these kinds of tricks are just boby level games, but if you did not have related training previously, you might not get the solution immediately. So, I will open a topic, or series, to record the algorithm questions I met or I played previously (10/03/2021, from my first algorithm article).

This series will include,

I will add more on this topic probably from my notes or practice code.

Introduction

This is the structure of this article,

  • Introduction
  • A - Question
  • B - Initial Solution
  • C - Good Solution

A - Question

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

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

  • -231 <= val <= 231 - 1
  • Methods Pop, Top and GetMin operations will always be called on non-empty stacks.
  • At most 3 * 104 calls will be made to push, pop, top, and getMin.

B - Solution 1

public class MinStack0 {
    private Stack stack;
    private int minValue; // minmum
    public MinStack0() {
        stack = new Stack();
    }
    public void Push(int value) {
        if (stack.Count == 0 || value <= minValue) {
            minValue = value;
        }
        stack.Push(value);
    }
    public void Pop() {
        if (stack.Count != 0) {
            if ((int) stack.Peek() == minValue) {
                Stack minStack0 = (Stack) stack.Clone();
                if (minStack0.Count > 1) // otherwise, it is a smallest one
                {
                    minStack0.Pop();
                    minValue = (int) minStack0.Peek();
                    while (minStack0.Count > 0) {
                        if ((int) minStack0.Peek() < minValue) minValue = (int) minStack0.Peek();
                        minStack0.Pop();
                    }
                }
            }
        }
        stack.Pop();
    }
    public int Top() {
        return (int) stack.Peek();
    }
    public int GetMin() {
        return minValue;
    }
}

Main Program

static void Main(string[] args) {
    MinStack minStack = new MinStack();
    minStack.Push(-2);
    minStack.Push(0);
    minStack.Push(-3);
    Console.WriteLine(minStack.GetMin()); // return -3
    minStack.Pop();
    Console.WriteLine(minStack.Top()); // return 0
    Console.WriteLine(minStack.GetMin()); // return -2
}

For the solution, Method Push, Top and GetMin are straightforward, only for Method Top, we need to handle, in the case, the top item is the smallest one, then after Pop, we need to get a new "smallest" value, which is done by the logic in the code above that we clone a current Stack, then get one by one to compare to each other and get the smallest value.

I thought this method might make the speed slower, therefore, I got another solution below, using two Stacks to handle the logic from top. However, both of them pass the test of, say, Min Stack --- leetcode.com. They are both good, and accepted. 

C - Solution 2

​public class MinStack {
    private Stack stack;
    private Stack minStack; // hold the minmum for each layer
    private int minValue; // minmum
    public MinStack() {
        stack = new Stack();
        minStack = new Stack();
    }
    public void Push(int value) {
        if (stack.Count == 0 || value <= minValue) {
            minValue = value;
            minStack.Push(value);
        }
        stack.Push(value);
    }
    public void Pop() {
        if (stack.Count != 0) {
            if ((int) stack.Peek() == minValue) {
                if (minStack.Count > 1) // otherwise, it is a smallest one
                    minStack.Pop();
                minValue = (int) minStack.Peek();
            }
        }
        stack.Pop();
    }
    public int Top() {
        return (int) stack.Peek();
    }
    public int GetMin() {
        return minValue;
    }
}​

Reference


Similar Articles