Zenn
📑

スライド最大問題のアルゴリズムをGolangで比較する

2024/05/11に公開
Go
Go
スライド最大問題
tech

はじめに

就活対策のために競プロを始めたのですが、D問題以降においてランタイムエラーに悩まされ、アルゴリズムの勉強をした方が良いと痛感した。
そこでABC352のD問題の復習も兼ねて「スライド最大問題」のアルゴリズムを紹介してランタイムを比較してみた。

スライド最大問題

ある配列A(長さN)が与えらえたときにi番目からi+K番目までの部分配列の最大値を要素b_iとする配列Bを作成せよ、という問題。

# example
## given
N = 5
K = 3
A = [3, 5, 1, 4, 2]

## way of thinking
b_1 = max(3, 5, 1) = 5
b_2 = max(5, 1, 4) = 5
b_3 = max(1, 4, 2) = 4

## answer
B = [5, 5, 4]

シンプルにMaxを使ったアルゴリズムの場合

考え方

素直に前述の思考に基づいて配列の最大値を取得する。

A = [3, 5, 1, 4, 2]
B = []

(i=1) : b_1 = max([3, 5, 1]) = 5
(i=2) : b_2 = max([5, 1, 4]) = 5
(i=3) : b_2 = max([1, 4, 3]) = 4

B = [5, 5, 4]

実装

配列長Nと窓サイズKに対してForループを計２重に利用しており、計算量はKN<=N^2となる。

func simpleMax(slice []int32, windowSize int32) []int32 {
	var maxSlice []int32
	for i := 0; i < len(slice)-int(windowSize); i++ {
		part := slice[i : i+int(windowSize)]
		max := int32(0)
		for _, v := range part {
			if v > max {
				max = v
			}
		}
		maxSlice = append(maxSlice, max)
	}
	return maxSlice
}

dequeを使ったアルゴリズムの場合

考え方

stack=(a_0, a_1, ..., a_i, ..., a_L)は以下のルールに従う

  1. 元の行列での順番を追い越してはいけない
    A = [1, 0, 2, 0, 3]ならばs=[1, 2, 3]は許容されるが[1, 3, 2]は許容されない
  2. stackは降順列である
    A = [3, 5, 1, 4, 2]ならばs=[5, 4, 2]は許容されるが[5, 1, 4]は許容されない
  3. stackにはwindow範囲外の要素は入れない
    A = [3, 5, 1, 4, 2], window = [1, 4, 2]ならばs=[4, 2]は許容されるが[5, 4, 2]は許容されない
A = [3, 5, 1, 4, 2]
B = []
stack = []

## rule1よりstackに要素を後ろから追加していくが, rule2, 3に低触する場合には適宜除去を行う
## rule2,3よりstack内はwindow内の要素が降順に並ぶ状態となるので先頭が最大値となる

### i=1 add [3, 5, 1] to stack
(i=1, step1) : s = [  ] + &3 -> [&3]
(i=1, step2) : s = [&3] + &5 -> [&3 ,&5] -> [&5] (rule2)
(i=1, step3) : s = [&5] + &1 -> [&5, &1]
(i=1       ) : b_1 = stack[0] = 5

### i=2 add 4 to stack
(i=2, step1) : s = [&5, &1] + &4 -> [&5    ] + &4 (rule2)
(i=2, step2) : s = [&5    ] + &4 -> [&5, &4]
(i=2       ) : b_1 = stack[0] = 5

### i=3 add 2 to stack
(i=2, step1) : s = [&5, &4] + &2 -> [&4    ] + &2 (rule3)
(i=2, step2) : s = [&4    ] + &2 -> [&4, &2]
(i=2       ) : b_1 = stack[0] = 4

B = [5, 5, 4]

実装

こちらも配列Nと待ち行列に対してForループを2重で使っているが、全体のアルゴリズムを考えると配列内の要素を待ち配列に入れて出す(計算量=1)という処理を１回ずつ行っているのみであるから全体の計算量はNとなる。

func slideWindowMax(slice []int32, windowSize int32) []int32 {
	var maxSlice []int32
	waitingStack := make([]int32, 0)
	for i := 0; i < len(slice)-int(windowSize); i++ {
		// remove from stack if value is out of window
		for {
			if len(waitingStack) == 0 || waitingStack[0] >= int32(i) {
				break
			}
			waitingStack = waitingStack[1:]
		}

		// remove from stack if new value is bigger than the last value
		for {
			if len(waitingStack) == 0 || slice[waitingStack[len(waitingStack)-1]] > slice[i] {
				break
			}
			waitingStack = waitingStack[:len(waitingStack)-1]
		}

		// add stack
		waitingStack = append(waitingStack, int32(i))
		// add max slice
		maxSlice = append(maxSlice, slice[waitingStack[0]])
	}
	return maxSlice
}

比較

stackめちゃくちゃ速いやん...

Discussion