07 · LIFO

Стек

Стек на слайсе решает скобки, вычисление выражений и монотонные задачи.

2 Go-примитива3 примераInterview 150

СНАЧАЛА ИНСТРУМЕНТЫ

Примитивы Go

Минимальный синтаксис, который понадобится в решении.

Push / pop

stack = append(stack, x)
top := stack[len(stack)-1]
stack = stack[:len(stack)-1]

Все операции с конца слайса амортизированно O(1).

Монотонный стек

for len(stack) > 0 && value > stack[len(stack)-1] {
    stack = stack[:len(stack)-1]
}
stack = append(stack, value)

Хранит элементы или индексы в монотонном порядке.

ПРАКТИКА

Примеры решений

Три идиоматичных решения на Go с оценкой времени и памяти.

ПРИМЕР РЕШЕНИЯ

Правильные скобки

Закрывающая скобка должна совпасть с вершиной.

O(n) time · O(n) space

solution.go

func isValid(s string) bool {
    pairs := map[byte]byte{')':'(', ']':'[', '}':'{'}
    stack := []byte{}
    for i := range s {
        if open, closing := pairs[s[i]]; closing {
            if len(stack) == 0 || stack[len(stack)-1] != open { return false }
            stack = stack[:len(stack)-1]
        } else { stack = append(stack, s[i]) }
    }
    return len(stack) == 0
}

ПРИМЕР РЕШЕНИЯ

Следующий тёплый день

Стек хранит индексы с убывающей температурой.

O(n) time · O(n) space

solution.go

func dailyTemperatures(t []int) []int {
    answer, stack := make([]int, len(t)), []int{}
    for day, temp := range t {
        for len(stack) > 0 && temp > t[stack[len(stack)-1]] {
            prev := stack[len(stack)-1]; stack = stack[:len(stack)-1]
            answer[prev] = day - prev
        }
        stack = append(stack, day)
    }
    return answer
}

ПРИМЕР РЕШЕНИЯ

Вычисление RPN

Операнд кладём в стек, оператор применяем к двум верхним значениям.

O(n) time · O(n) space

solution.go

func evalRPN(tokens []string) int {
    stack := []int{}
    for _, token := range tokens {
        if n, err := strconv.Atoi(token); err == nil {
            stack = append(stack, n); continue
        }
        b, a := stack[len(stack)-1], stack[len(stack)-2]
        stack = stack[:len(stack)-2]
        stack = append(stack, apply(token, a, b))
    }
    return stack[0]
}

ПЕРЕД КОДОМ

Чек-лист рассуждения

Проверяй стек перед обращением к вершине
Храни индексы, если нужна дистанция
Каждый элемент push/pop не более одного раза