【Golang】LeetCode-剣指Offer-面接問題30-min関数を含むスタック

テーマ
スタックのデータ構造を定義し、このタイプにおいて、スタックを得ることができる最小要素のmin関数を実現してください.このスタックにおいて、min、pushおよびpopを呼び出す時間の複雑さはすべてO(1)です.
例:
MinStock minStock=new MinStock();minStock.push(-2)minStock.push(0)minStock.push(-3)minStock.min()－>は-3.minStock.pop()を返します.minStock.top()>>0を返します.minStock.min();>.は-2を返します
ヒント:各関数の呼び出しの合計回数は20000回を超えません.
ソース:スナップリンク:https://leetcode-cn.com/problems/bao-han-minhan-shu-de-zhan-lcof
問題を解く構想
暴力法:minを呼び出すとスタックを巡回して、その中の最小の数値を探し出します.ここでは問題の要求に合わず、デモンストレーションをしません.
スタック

特徴:先進後

を出す.

テーマの中で実現する方法が必要です.

push():配列の最後に1つ以上の要素(押し込みスタック)

を追加します.

top():配列の最後の要素(スタックトップ要素)を返しますが、スタック

は出ません.

pop():配列の最後の要素を削除する

問題を解く
min関数を含むスタックは、つまりスタックより1 min多くなり、呼び出したらスタックの最小値に戻ります.
したがって、補助スタックのスタックtopは最小値であるmin()を呼び出して、より小さい値を記憶するために補助スタックを追加する必要があるだけである.
コード
–実行時間:24 ms--消費メモリ:8.5 MB

type MinStack struct {
    nums []int 	//   
    min []int 	//     ，     
}

/** initialize your data structure here. */
func Constructor() MinStack {
    return MinStack{
        make([]int,0,3),
        make([]int,0,3),
    }
}

func (this *MinStack) Push(x int)  {
    this.nums=append(this.nums,x)
    if len(this.min)==0{
        this.min=append(this.min,x)
    }else if this.min[len(this.min)-1]<x{
        this.min=append(this.min,this.min[len(this.min)-1])
    }else{
        this.min=append(this.min,x)
    }
}


func (this *MinStack) Pop()  {
    this.nums=this.nums[:len(this.nums)-1]
    this.min=this.min[:len(this.min)-1]
}


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


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

/**
 * Your MinStack object will be instantiated and called as such:
 * obj := Constructor();
 * obj.Push(x);
 * obj.Pop();
 * param_3 := obj.Top();
 * param_4 := obj.Min();
 */

LeetCodeのこの問題の中で、私も問題解を提出しました.確認してください.ニックネーム:Sakura.