首页 > itarticle > Min Stack

Min Stack

admin 11月 13, 2020 0

题目描述

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.

解题思路

使用数组保存所有元素
一个len记录stack中元素数目

Go实现

package main

import "fmt"

type MinStack struct {
    stack []int
    len int
}



func () MinStack {
    s := new(MinStack)
    return *s
}


func (this *MinStack) Push(x int)  {
        this.stack = append(this.stack, x)
        this.len++
}


func (this *MinStack) Pop()  {
    this.len--
    this.stack = this.stack[0:this.len]
}


func (this *MinStack) Top() int {
    if this.len>0{
        return this.stack[this.len-1]
    }else{
        panic("stack empty")
    }
}


func (this *MinStack) GetMin() int {
    minVal := 2147483647
    n := this.len-1

    for n >=0 {
        if this.stack[n] < minVal{
            minVal = this.stack[n]
        }
        n--

    }
    return minVal
}


func main()  {

    s := new(MinStack)
    s.Push(-2)
    s.Push(0)
    s.Push(-3)
    fmt.Println(s.GetMin())
    s.Pop()
    fmt.Println(s.Top())
    fmt.Println(s.GetMin())
}