Разработка структуры данных для поддержки операций со стеком и поиска минимума

Question

Вопрос для интервью: спроектируйте структуру данных, которая имеет следующие особенности

• нажмите данные
• выскакивает последние вставленные данные [LIFO]
• Дает минимум

Все вышеперечисленные операции должны иметь сложность O(1)

Answer 1

Вы можете сделать это, поддерживая два стека

stack - выполнять обычные операции push и pop для этого стека.

minStack - этот стек используется для получения минимального элемента в стеке за O(1) время. В любой момент верхний элемент этого стека будет минимальным из всех элементов стека.

push( item a) 
    // push the element on the stack.
    stack.push(a)   

    // find the min of the ele to be pushed and the ele on top of minStack.
    if(minStack.isEmpty()) 
        min = a
    else
        min = Min(a,minStack.top())

    // push the min ele on the minStack.
    minStack.push(min) 
end push


pop()
    // pop and discard
    minStack.pop() 

    // pop and return
    return stack.pop() 
end pop


findMin()
    return minStack.top()
end findMin

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

push( item a) 
    // push the element on the orginal stack.
    stack.push(a)   

    if(minStack.isEmpty())
            // if minStack is empty push.
            minStack.push(a) 
    // else push only if the element is less than or equal to the present min.
    else if(a <= minStack.top()) 
        minStack.push(a)
end push

pop()
    // pop from the stack
    ele = stack.top()     
    if(minStack.top() == ele)
            // pop only if the top element is ele.
        minStack.pop() 

    // return the popped element.
    return ele 
end pop

Answer 2

Для этого ваша структура данных должна содержать два стека. Нужно функционировать как обычно; другой содержит только последний видимый минимальный элемент. Когда вы помещаете элемент, если он меньше или равен вершине второго стека (или стек пуст), также вставьте его во второй стек Когда вы выталкиваете элемент, если он равен вершине второго стека, тоже выталкиваете второй стек.

Минимум в любое время - вершина второго стека.

Answer 3

Этот вопрос фактически задает Heap

PriorityQueue - это классический случай (реализация Heap).См. java.util.PriorityQueue

Хотелось бы, чтобы в Интернете был простой способ ссылки на исходный код языка Java, где я могу увидеть и обратиться к реализации класса PriorityQueue.

Answer 4

Существует более креативное решение без использования вспомогательного стека.

Предположим, что мы собираемся поместить число значение в стек с минимальным числом min . Если значение больше или равно мин , оно помещается непосредственно в стек данных. Если оно меньше мин , мы нажимаем 2 ** значение * - мин и обновляем мин как значение , так как новый минимум номер выдвинут.

Как насчет поп? Мы извлекаем его напрямую, если вершина стека данных (она обозначается как top ) больше или равна min . В противном случае число top не является действительным введенным числом. Действительное введенное число сохраняется как min . После того, как текущий минимальный номер вытолкнут, нам нужно восстановить предыдущий минимальный номер, который составляет 2 ** мин * - top .

Теперь давайте продемонстрируем правильность этого решения. Когда значение больше или равно мин , оно помещается в стек данных напрямую без обновления мин . Следовательно, когда мы обнаруживаем, что вершина стека данных больше или равна min , мы можем получить всплывающее окно без обновления min . Однако, если мы находим значение меньше, чем мин , мы нажимаем 2 значение * - мин . Следует отметить, что значение 2 * - min меньше value . Затем мы обновляем текущее значение мин как значение . Поэтому новая вершина стека данных ( top ) меньше текущей min . Следовательно, когда мы находим, что вершина стека данных меньше мин , реальная вершина (действительное нажатое число значение ) сохраняется в мин . После того, как мы вытолкнули вершину стека данных, мы должны восстановить предыдущее минимальное число. Поскольку top = 2 ** значение * -предыдущее min и значение является текущим min , предыдущее min равно 2 * текущий мин - топ .

Пример кода C ++ показан ниже:

template <typename T> class StackWithMin {
public:
    StackWithMin(void) {}
    virtual ~StackWithMin(void) {}

    T& top(void);
    void push(const T& value);
    void pop(void);
    const T& min(void) const;

private:
    std::stack<T>   m_data;     // data stack, to store numbers
    T               m_min;      // minimum number
};

template <typename T> void StackWithMin<T>::push(const T& value) {
    if(m_data.size() == 0) {
        m_data.push(value);
        m_min = value;
    }
    else if(value >= m_min) {
        m_data.push(value);
    }
    else {
        m_data.push(2 * value - m_min);
        m_min = value;
    }
}

template <typename T> void StackWithMin<T>::pop() {
    assert(m_data.size() > 0);

    if(m_data.top() < m_min)
        m_min = 2 * m_min - m_data.top();

    m_data.pop();
}

template <typename T> const T& StackWithMin<T>::min() const {
    assert(m_data.size() > 0);

    return m_min;
}

template <typename T> T& StackWithMin<T>::top() {
    T top = m_data.top();
    if(top < m_min)
        top = m_min;

    return top;
}

Это решение заимствовано из моего блога и моей книги " Интервью по кодированию: вопросы, анализ и решения ".