Задача: 341. Flatten Nested List Iterator
Сложность: medium

Дан вложенный список, содержащий либо числа, либо списки. Нужно реализовать итератор, который будет плоско проходить по всем числам в порядке их появления.

Пример:

Input: nestedList = [[1,1],2,[1,1]]
Output: [1,1,2,1,1]
Explanation: By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,1,2,1,1].

👨‍💻 Алгоритм:

1⃣Инициализация
Сохраняйте исходный вложенный список в стеке или очереди. Используйте стек для сохранения состояния итерации по вложенным спискам.

2⃣Метод next()
Возвращает следующий целый элемент из стека или очереди. Если текущий элемент является списком, развёртывайте его и добавляйте элементы в стек.

3⃣Метод hasNext()
Проверяет, есть ли в стеке или очереди оставшиеся целые элементы. Если на вершине стека находится список, развёртывайте его до тех пор, пока не встретится целый элемент.

😎 Решение:

class NestedIterator {
    private $stack;
    
    function __construct($nestedList) {
        $this->stack = [];
        $this->flatten($nestedList);
    }
    
    private function flatten($nestedList) {
        for ($i = count($nestedList) - 1; $i >= 0; $i--) {
            array_push($this->stack, $nestedList[$i]);
        }
    }
    
    function next() {
        return array_pop($this->stack)->getInteger();
    }
    
    function hasNext() {
        while (!empty($this->stack) && !$this->stack[count($this->stack) - 1]->isInteger()) {
            $this->flatten(array_pop($this->stack)->getList());
        }
        return !empty($this->stack);
    }
}

Ставь 👍 и забирай 📚 Базу знаний