最小値をO(1)で返すスタックの実装

概要

前の記事でGoによるスタックの実装を紹介しました。

shoman.hatenablog.com

そんな中でCracking the Coding Interviewの3.2の問題で以下のようなものがありました。

問題

pushとpopに加えて、最小の要素を返す関数minを持つスタックをどのようにデザインしますか？ただしpush, pop, min関数はすべての実行時間になるようにしてください。

世界で闘うプログラミング力を鍛える本 ~コーディング面接189問とその解法~

pushまたはpopする際に毎回最小値を探していると、実行時間はになってしまい条件に合いません。

で最小値を得るためには、スタックの各要素に、その要素以下における最小値を保存しておけば良いです。

解法

前回実装したスタックを少し修正します。

type Stack 修正前

type Stack []int

type Stack 修正後

type data struct {
    val int
    min int
}

スタックに格納するintとともに、その要素以下の最小値minをスタックに積みます。

Push 修正前

func (s *Stack) Push(v int) {
    *s = append(*s, v)
}

Push 修正後

func (s *Stack) Push(v int) {
    min, err := s.Min()
    if err == nil && v < min {
        min = v
    }
    d := data{v, min}
    *s = append(*s, d)
}

要素をpushする際に、push前のトップの要素に含まれる最小値と、新たにpushする値を比較します。 新たな値の方が小さい場合はそれを新たな要素のminとし、 新たな値の方が大きい場合はpush前のトップのminを新たな要素のminとします。

Min 追加

func (s *Stack) Min() (int, error) {
    if s.Empty() {
        return 0, fmt.Errorf("stack is empty")
    }

    return (*s)[len(*s)-1].min, nil
}

トップ要素のminを返します。

実行例

func main() {
    s := GenStack()

    s.Push(0)
    s.Push(-1)
    s.Push(1)
    fmt.Println(*s) // [{0 0} {-1 -1} {1 -1}]

    min, _ := s.Min()
    fmt.Println(min) // -1
}

コメント

• 最小値を保存しておく別のスタックを用意し、更新されたときだけpush, popする解法もあります