155. Min Stack

Problem Link

Use two stacks: one stack (\(storeStk\)) to hold all the pushed values, and another stack (\(minStk\)) to track only the candidate minimum values, with the current minimum always at the top.

• Push: Push the value into \(storeStk\). Also push it into \(minStk\) if \(minStk\) is empty or the value is less than or equal to the current top of \(minStk\).
• Pop: Pop the top element from \(storeStk\). If the popped value is equal to the top of \(minStk\), pop from \(minStk\) as well.
• GetMin: Return the top element of \(minStk\).

Runtime Complexity

Time: \(O(1)\)

Space: \(O(n)\)

PythonGo

class MinStack:

    def __init__(self):
        self.min_stk = []
        self.store_stk = []

    def push(self, val: int) -> None:
        if len(self.store_stk) == 0 or self.min_stk[-1] >= val:
            self.min_stk.append(val)
        self.store_stk.append(val)

    def pop(self) -> None:
        if len(self.store_stk) == 0:
            return

        val = self.store_stk.pop()
        if val == self.min_stk[-1]:
            self.min_stk.pop()

    def top(self) -> int:
        if len(self.store_stk) != 0:
            return self.store_stk[-1]

    def getMin(self) -> int:
        if len(self.store_stk) != 0:
            return self.min_stk[-1]

type MinStack struct {
    minStk   []int
    storeStk []int
}

func Constructor() MinStack {
    var stk MinStack
    return stk
}

func (this *MinStack) Push(val int) {
    if len(this.minStk) == 0 || this.minStk[len(this.minStk)-1] >= val {
        this.minStk = append(this.minStk, val)
    }
    this.storeStk = append(this.storeStk, val)
}

func (this *MinStack) Pop() {
    if len(this.storeStk) != 0 {
        ls, lm := len(this.storeStk), len(this.minStk)
        val := this.storeStk[ls-1]
        if val == this.minStk[lm-1] {
            this.minStk = this.minStk[:lm-1]
        }
        this.storeStk = this.storeStk[:ls-1]
    }
}

func (this *MinStack) Top() int {
    return this.storeStk[len(this.storeStk)-1]
}

func (this *MinStack) GetMin() int {
    return this.minStk[len(this.minStk)-1]
}

---