leetcode: максимальное значение очереди

алгоритм

тема:

Пожалуйста, определите очередь и реализуйте функцию max_value, чтобы получить максимальное значение в очереди Амортизированная временная сложность функций max_value, push_back и pop_front равна O(1). 

Если очередь пуста, pop_front и max_value должны возвращать -1

отвечать:

class MaxQueue {
    Queue<Integer> q;
    Deque<Integer> d;

    public MaxQueue() {
        q = new LinkedList<Integer>();
        d = new LinkedList<Integer>();
    }
    
    public int max_value() {
        if (d.isEmpty()) {
            return -1;
        }
        return d.peekFirst();
    }
    
    public void push_back(int value) {
        while (!d.isEmpty() && d.peekLast() < value) {
            d.pollLast();
        }
        d.offerLast(value);
        q.offer(value);
    }
    
    public int pop_front() {
        if (q.isEmpty()) {
            return -1;
        }
        int ans = q.poll();
        if (ans == d.peekFirst()) {
            d.pollFirst();
        }
        return ans;
    }
}

Идеи решения проблемы:

Этот алгоритм основан на важном свойстве задачи: когда элемент поставлен в очередь, все предшествующие ему элементы, которые меньше его, больше не будут влиять на ответ. Например, если мы вставим в очередь последовательность чисел 1 1 1 1 2, то после вставки первого числа 2 все числа 1 перед числом 2 не будут влиять на результат. Потому что согласно порядку выноса очереди номер 2 может быть вынут только после того, как будут вынуты все номера 1, поэтому если номер 1 стоит в очереди, то номер 2 тоже должен быть в очереди. очереди, чтобы число 1 не повлияло на результат. 

В соответствии с вышеприведенной идеей мы можем разработать такой метод: при вставке элемента с конца очереди мы можем заранее вынуть из очереди все элементы, которые меньше этого элемента, так что только числа, которые влияют результат сохраняется в очереди. Такой метод эквивалентен требованию поддерживать монотонно убывающую очередь, то есть гарантировать, что каждому элементу не предшествует элемент, меньший, чем он.

Так как же эффективно реализовать очередь, которая всегда уменьшается? Нам нужно только брать элементы меньше текущего значения элемента из хвоста очереди по очереди при вставке каждого значения элемента, пока не встретится значение элемента больше, чем текущий элемент. Вышеупомянутая процедура гарантирует, что, пока очередь уменьшается до вставки значения элемента, очередь по-прежнему уменьшается после вставки значения. А начальное состояние очереди (пустая очередь) соответствует определению монотонно убывающей. По математической индукции очередь всегда будет оставаться монотонно убывающей. Вышеупомянутый процесс должен брать элементы из хвоста очереди, поэтому его необходимо реализовать с использованием двусторонней очереди. Кроме того, нам также нужна вспомогательная очередь для записи всех вставленных значений, чтобы определить возвращаемое значение функции pop_front. Убедившись, что очередь монотонно убывает, нужно напрямую взять только первый элемент в двусторонней очереди, чтобы найти максимальное значение. 

понимать:

Убедитесь, что сортировка вспомогательной очереди уменьшается от начала к концу. В этом случае передний элемент каждой очереди является самым большим элементом. Когда вы хотите вынуть его, вы можете напрямую вынуть первый элемент очереди. Метод реализации состоит в том, чтобы каждый раз вставлять элементы из конца очереди. В это время, пока есть элементы меньшего размера, чем этот элемент впереди, используйте метод deque removeRear() для удаления элементов из конца очереди, чтобы удалить эти элементы. deque — это двусторонняя очередь, которая была представлена ​​в предыдущей статье.

Категории