Реализуйте очередь, в которой push_rear(), pop_front() и get_min() - все операции с постоянным временем
Я сталкивался с таким вопросом:реализовать очередь, в которой push_rear (), pop_front () и get_min () - все операции с постоянным временем.
Сначала я подумал об использовании структуры данных с минимальной кучей, которая имеет сложность O (1) для get_min(). Но push_rear () и pop_front () будут O (log (n)).
Кто-нибудь знает, что было бы лучшим способом реализовать такую очередь, которая имеет O (1) push (), pop () и min ()?
Я гуглил об этом и хотел указать на этот поток Алгоритм вундеркиндов. Но похоже, что ни одно из решений не следует правилу постоянного времени для всех трех методов: push (), pop () и min().
Спасибо за все предложения.
12 ответов
Вы можете реализовать стек с помощью O(1) pop(), push() и get_min(): просто сохраните текущий минимум вместе с каждым элементом. Так, например, стек [4,2,5,1] (1 сверху) становится [(4,4), (2,2), (5,2), (1,1)],
Затем вы можете использовать два стека для реализации очереди. Нажмите на один стек, поп с другого; если во время всплытия второй стек пуст, переместите все элементы из первого стека во второй.
Например, для pop запрос, перемещая все элементы из первого стека [(4,4), (2,2), (5,2), (1,1)]второй стек будет [(1,1), (5,1), (2,1), (4,1)], и теперь верните верхний элемент из второго стека.
Чтобы найти минимальный элемент очереди, посмотрите на наименьшие два элемента отдельных минимальных стеков, а затем возьмите минимум из этих двух значений. (Конечно, здесь есть некоторая дополнительная логика, если один из стеков пуст, но это не так уж сложно обойти).
Будет иметь O (1) get_min() а также push() и амортизированный O (1) pop(),
Хорошо, я думаю, что у меня есть ответ, который дает вам все эти операции в амортизированном O(1), означая, что любая операция может занять до O(n), но любая последовательность из n операций занимает O (1) время на операцию,
Идея состоит в том, чтобы хранить ваши данные в виде декартового дерева. Это двоичное дерево, подчиняющееся свойству min-heap (каждый узел не больше его дочерних элементов) и упорядочено таким образом, что обход узлов по порядку возвращает вам узлы в том же порядке, в котором они были добавлены. Например, вот декартово дерево для последовательности 2 1 4 3 5:
1
/ \
2 3
/ \
4 5
Можно вставить элемент в декартово дерево за время амортизации O(1), используя следующую процедуру. Посмотрите на правый корешок дерева (путь от корня до самого правого листа, образованного всегда ходьбой вправо). Начиная с самого правого узла, сканируйте вверх по этому пути, пока не найдете первый узел меньше, чем узел, который вы вставляете.
Измените этот узел так, чтобы его правый дочерний узел был этим новым узлом, а затем сделайте прежний правый дочерний узел этого узла левым дочерним узлом только что добавленного узла. Например, предположим, что мы хотим вставить еще одну копию 2 в вышеприведенное дерево. Мы идем вверх по правому отделу позвоночника мимо 5 и 3, но останавливаемся ниже 1, потому что 1 < 2. Затем мы меняем дерево так:
1
/ \
2 2
/
3
/ \
4 5
Обратите внимание, что обход по порядку дает 2 1 4 3 5 2, то есть последовательность, в которой мы добавили значения.
Это выполняется в амортизированной O(1), потому что мы можем создать потенциальную функцию, равную количеству узлов в правой части дерева. Реальное время, необходимое для вставки узла, равно 1 плюс количество узлов в позвоночнике, которое мы рассматриваем (назовите это k). Как только мы находим место для вставки узла, размер позвоночника уменьшается на длину k - 1, поскольку каждый из k узлов, которые мы посетили, больше не находится на правом позвоночнике, а новый узел находится на своем месте. Это дает амортизированную стоимость 1 + k + (1 - k) = 2 = O(1) для амортизированной вставки O(1). В качестве другого способа думать об этом, когда узел перемещен с правого отдела позвоночника, он больше никогда не является частью правого отдела позвоночника, и поэтому нам больше никогда не придется его перемещать. Поскольку каждый из n узлов может быть перемещен не более одного раза, это означает, что n вставок может выполнить не более n перемещений, поэтому общее время выполнения составляет не более O (n) для амортизированного O (1) на элемент.
Чтобы сделать шаг удаления, мы просто удаляем самый левый узел из декартового дерева. Если этот узел является листом, мы закончили. В противном случае у узла может быть только один дочерний элемент (правильный дочерний элемент), поэтому мы заменяем узел его правым дочерним элементом. При условии, что мы отслеживаем, где находится самый левый узел, этот шаг занимает O (1) времени. Однако после удаления самого левого узла и замены его правым дочерним узлом мы можем не знать, где находится новый самый левый узел. Чтобы это исправить, мы просто идем по левому корешку дерева, начиная с нового узла, который мы только что переместили к самому левому дочернему элементу. Я утверждаю, что это все еще работает в O (1) амортизированном времени. Чтобы убедиться в этом, я утверждаю, что узел посещается не более одного раза во время любого из этих проходов, чтобы найти самый левый узел. Чтобы увидеть это, обратите внимание, что после того, как узел был посещен таким образом, единственный способ, которым нам когда-либо понадобится посмотреть на него снова, будет, если он будет перемещен из дочернего элемента самого левого узла в крайний левый узел. Но все посещенные узлы являются родителями самого левого узла, поэтому этого не может быть. Следовательно, каждый узел посещается не более одного раза в течение этого процесса, и всплывающее окно работает в O(1).
Мы можем сделать find-min в O(1), потому что декартово дерево дает нам доступ к наименьшему элементу дерева бесплатно; это корень дерева.
Наконец, чтобы увидеть, что узлы возвращаются в том же порядке, в котором они были вставлены, обратите внимание, что декартово дерево всегда хранит свои элементы, так что обход по порядку посещает их в отсортированном порядке. Так как мы всегда удаляем самый левый узел на каждом шаге, и это первый элемент прохождения по порядку, мы всегда возвращаем узлы в том порядке, в котором они были вставлены.
Короче говоря, мы получаем O (1) амортизированные push и pop и O (1) find-min наихудшего случая.
Если я смогу предложить реализацию O (1) в худшем случае, я обязательно опубликую ее. Это была большая проблема; спасибо за публикацию!
Хорошо, вот одно решение.
Сначала нам понадобятся некоторые вещи, которые обеспечивают push_back(),push_front(),pop_back() и pop_front () в 0(1). Это легко реализовать с помощью массива и двух итераторов. Первый итератор будет указывать на фронт, второй на тыл. Давайте назовем такие вещи deque.
Вот псевдокод:
class MyQueue//Our data structure
{
deque D;//We need 2 deque objects
deque Min;
push(element)//pushing element to MyQueue
{
D.push_back(element);
while(Min.is_not_empty() and Min.back()>element)
Min.pop_back();
Min.push_back(element);
}
pop()//poping MyQueue
{
if(Min.front()==D.front() )
Min.pop_front();
D.pop_front();
}
min()
{
return Min.front();
}
}
Объяснение:
Пример давайте нажмем цифры [12,5,10,7,11,19] и на наш MyQueue
1) толкая 12
D [12]
Min[12]
2) толкая 5
D[12,5]
Min[5] //5>12 so 12 removed
3) толкая 10
D[12,5,10]
Min[5,10]
4) толкая 7
D[12,5,10,7]
Min[5,7]
6) толкая 11
D[12,5,10,7,11]
Min[5,7,11]
7) толкая 19
D[12,5,10,7,11,19]
Min[5,7,11,19]
Теперь давайте вызовем pop_front ()
у нас есть
D[5,10,7,11,19]
Min[5,7,11,19]
Минимум 5
Давайте снова вызовем pop_front ()
Объяснение: pop_front удалит 5 из D, но также вытолкнет передний элемент Min, потому что он равен переднему элементу D (5).
D[10,7,11,19]
Min[7,11,19]
И минимум 7.:)
Используйте одну деку (A) для хранения элементов и другую деку (B) для хранения минимумов.
Когда x ставится в очередь, отправьте его обратно в A и сохраняйте pop_backing B до тех пор, пока задняя часть B не станет меньше x, затем нажмите push_back x в B.
при отмене A pop_front A в качестве возвращаемого значения, а если оно равно фронту B, pop_front B также.
при получении минимума A используйте фронт B в качестве возвращаемого значения.
dequeue и getmin, очевидно, O(1). Для операции постановки в очередь рассмотрим push_back из n элементов. Существует n push_back для A, n push_back для B и не более n pop_back для B, потому что каждый элемент либо останется в B, либо будет извлечен один раз из B. В общем, существует O(3n) операций, и поэтому амортизированная стоимость равна O (1), а также для постановки в очередь.
Наконец, причина того, что этот алгоритм работает, состоит в том, что когда вы ставите x в очередь A, если в B есть элементы, которые больше x, они никогда не будут минимальными, потому что x будет оставаться в очереди A дольше, чем любые элементы в B (очередь это FIFO). Поэтому нам нужно выдвинуть элементы в B (сзади), которые больше, чем x, прежде чем мы введем x в B.
from collections import deque
class MinQueue(deque):
def __init__(self):
deque.__init__(self)
self.minq = deque()
def push_rear(self, x):
self.append(x)
while len(self.minq) > 0 and self.minq[-1] > x:
self.minq.pop()
self.minq.append(x)
def pop_front(self):
x = self.popleft()
if self.minq[0] == x:
self.minq.popleft()
return(x)
def get_min(self):
return(self.minq[0])
Если вы не против сохранить немного дополнительных данных, хранить минимальное значение будет тривиально. Push и pop могут обновлять значение, если новый или удаленный элемент является минимальным, и возвращать минимальное значение так же просто, как получить значение переменной.
Это предполагает, что get_min() не изменяет данные; если вы предпочитаете что-то вроде pop_min() (т.е. удалите минимальный элемент), вы можете просто сохранить указатель на фактический элемент и предшествующий ему элемент (если есть) и обновить их соответствующим образом с помощью push_rear() и pop_front() также.
Редактировать после комментариев:
Очевидно, что это приводит к O(n) push и pop в случае, если минимум изменяется на этих операциях, и поэтому не строго удовлетворяет требованиям.
Решения этого вопроса, включая код, можно найти здесь: http://discuss.joelonsoftware.com/default.asp?interview.11.742223.32
Вы можете использовать LinkedList для поддержки очереди.
Каждый элемент в LinkedList будет иметь тип
class LinkedListElement
{
LinkedListElement next;
int currentMin;
}
У вас может быть два указателя. Один указывает на начало, а другой - на конец.
Если вы добавляете элемент в начало очереди. Изучите указатель начала и узел для вставки. Если узел для вставки currentmin меньше, чем запуск узла currentmin, для вставки currentmin это минимум. Иначе обновите currentmin с запуском currentmin.
Повторите то же самое для enque.
Реализация JavaScript
( Отдайте должное решению Adamax за идею; я свободно основал реализацию на нем. Перейдите к основанию, чтобы увидеть полностью прокомментированный код или прочитайте общие шаги ниже. Обратите внимание, что это находит максимальное значение в постоянном времени O(1), а не минимальное значение - легко изменить):
Общая идея заключается в создании двух стеков при построении
MaxQueue(Я использовал связанный список в качестве основногоStackструктура данных - не включена в код; но любойStackбудет делать до тех пор, пока это реализовано с помощью O(1) вставки / удаления). Один мы будем в основномpopот (dqStack) и один мы будем в основномpushк (eqStack).
Вставка: O(1) худший случай
За
enqueueеслиMaxQueueпусто, мы будемpushзначение дляdqStackнаряду с текущим максимальным значением в кортеже (то же значение, так как это единственное значение вMaxQueue); например:
const m = new MaxQueue();
m.enqueue(6);
/*
the dqStack now looks like:
[6, 6] - [value, max]
*/
Если
MaxQueueне пусто, мыpushпросто значение дляeqStack;
m.enqueue(7);
m.enqueue(8);
/*
dqStack: eqStack: 8
[6, 6] 7 - just the value
*/
Затем обновите максимальное значение в кортеже.
/*
dqStack: eqStack: 8
[6, 8] 7
*/
Удаление: O(1) амортизируется
За
dequeueЧто жpopотdqStackи вернуть значение из кортежа.
m.dequeue();
> 6
// equivalent to:
/*
const tuple = m.dqStack.pop() // [6, 8]
tuple[0];
> 6
*/
Тогда, если
dqStackпусто, переместить все значения вeqStackвdqStackНапример:
// if we build a MaxQueue
const maxQ = new MaxQueue(3, 5, 2, 4, 1);
/*
the stacks will look like:
dqStack: eqStack: 1
4
2
[3, 5] 5
*/
По мере перемещения каждого значения мы будем проверять, превышает ли оно максимальное значение, и сохраняем его в каждом кортеже:
maxQ.dequeue(); // pops from dqStack (now empty), so move all from eqStack to dqStack
> 3
// as dequeue moves one value over, it checks if it's greater than the ***previous max*** and stores the max at tuple[1], i.e., [data, max]:
/*
dqStack: [5, 5] => 5 > 4 - update eqStack:
[2, 4] => 2 < 4 - no update
[4, 4] => 4 > 1 - update
[1, 1] => 1st value moved over so max is itself empty
*/
Потому что каждое значение перемещается в
dqStackсамое большее, мы можем сказать, чтоdequeueимеет O(1) амортизированную временную сложность.
Нахождение максимального значения: O(1) худший случай
Затем в любой момент времени мы можем позвонить
getMaxполучить текущее максимальное значение в O(1) постоянное время. ПокаMaxQueueне пусто, максимальное значение легко извлекается из следующего кортежа вdqStack,
maxQ.getMax();
> 5
// equivalent to calling peek on the dqStack and pulling out the maximum value:
/*
const peekedTuple = maxQ.dqStack.peek(); // [5, 5]
peekedTuple[1];
> 5
*/
Код
class MaxQueue {
constructor(...data) {
// create a dequeue Stack from which we'll pop
this.dqStack = new Stack();
// create an enqueue Stack to which we'll push
this.eqStack = new Stack();
// if enqueueing data at construction, iterate through data and enqueue each
if (data.length) for (const datum of data) this.enqueue(datum);
}
enqueue(data) { // O(1) constant insertion time
// if the MaxQueue is empty,
if (!this.peek()) {
// push data to the dequeue Stack and indicate it's the max;
this.dqStack.push([data, data]); // e.g., enqueue(8) ==> [data: 8, max: 8]
} else {
// otherwise, the MaxQueue is not empty; push data to enqueue Stack
this.eqStack.push(data);
// save a reference to the tuple that's next in line to be dequeued
const next = this.dqStack.peek();
// if the enqueueing data is > the max in that tuple, update it
if (data > next[1]) next[1] = data;
}
}
moveAllFromEqToDq() { // O(1) amortized as each value will move at most once
// start max at -Infinity for comparison with the first value
let max = -Infinity;
// until enqueue Stack is empty,
while (this.eqStack.peek()) {
// pop from enqueue Stack and save its data
const data = this.eqStack.pop();
// if data is > max, set max to data
if (data > max) max = data;
// push to dequeue Stack and indicate the current max; e.g., [data: 7: max: 8]
this.dqStack.push([data, max]);
}
}
dequeue() { // O(1) amortized deletion due to calling moveAllFromEqToDq from time-to-time
// if the MaxQueue is empty, return undefined
if (!this.peek()) return;
// pop from the dequeue Stack and save it's data
const [data] = this.dqStack.pop();
// if there's no data left in dequeue Stack, move all data from enqueue Stack
if (!this.dqStack.peek()) this.moveAllFromEqToDq();
// return the data
return data;
}
peek() { // O(1) constant peek time
// if the MaxQueue is empty, return undefined
if (!this.dqStack.peek()) return;
// peek at dequeue Stack and return its data
return this.dqStack.peek()[0];
}
getMax() { // O(1) constant time to find maximum value
// if the MaxQueue is empty, return undefined
if (!this.peek()) return;
// peek at dequeue Stack and return the current max
return this.dqStack.peek()[1];
}
}Реализация Java
import java.io.*;
import java.util.*;
public class queueMin {
static class stack {
private Node<Integer> head;
public void push(int data) {
Node<Integer> newNode = new Node<Integer>(data);
if(null == head) {
head = newNode;
} else {
Node<Integer> prev = head;
head = newNode;
head.setNext(prev);
}
}
public int pop() {
int data = -1;
if(null == head){
System.out.println("Error Nothing to pop");
} else {
data = head.getData();
head = head.getNext();
}
return data;
}
public int peek(){
if(null == head){
System.out.println("Error Nothing to pop");
return -1;
} else {
return head.getData();
}
}
public boolean isEmpty(){
return null == head;
}
}
static class stackMin extends stack {
private stack s2;
public stackMin(){
s2 = new stack();
}
public void push(int data){
if(data <= getMin()){
s2.push(data);
}
super.push(data);
}
public int pop(){
int value = super.pop();
if(value == getMin()) {
s2.pop();
}
return value;
}
public int getMin(){
if(s2.isEmpty()) {
return Integer.MAX_VALUE;
}
return s2.peek();
}
}
static class Queue {
private stackMin s1, s2;
public Queue(){
s1 = new stackMin();
s2 = new stackMin();
}
public void enQueue(int data) {
s1.push(data);
}
public int deQueue() {
if(s2.isEmpty()) {
while(!s1.isEmpty()) {
s2.push(s1.pop());
}
}
return s2.pop();
}
public int getMin(){
return Math.min(s1.isEmpty() ? Integer.MAX_VALUE : s1.getMin(), s2.isEmpty() ? Integer.MAX_VALUE : s2.getMin());
}
}
static class Node<T> {
private T data;
private T min;
private Node<T> next;
public Node(T data){
this.data = data;
this.next = null;
}
public void setNext(Node<T> next){
this.next = next;
}
public T getData(){
return this.data;
}
public Node<T> getNext(){
return this.next;
}
public void setMin(T min){
this.min = min;
}
public T getMin(){
return this.min;
}
}
public static void main(String args[]){
try {
FastScanner in = newInput();
PrintWriter out = newOutput();
// System.out.println(out);
Queue q = new Queue();
int t = in.nextInt();
while(t-- > 0) {
String[] inp = in.nextLine().split(" ");
switch (inp[0]) {
case "+":
q.enQueue(Integer.parseInt(inp[1]));
break;
case "-":
q.deQueue();
break;
case "?":
out.println(q.getMin());
default:
break;
}
}
out.flush();
out.close();
} catch(IOException e){
e.printStackTrace();
}
}
static class FastScanner {
static BufferedReader br;
static StringTokenizer st;
FastScanner(File f) {
try {
br = new BufferedReader(new FileReader(f));
} catch (FileNotFoundException e) {
e.printStackTrace();
}
}
public FastScanner(InputStream f) {
br = new BufferedReader(new InputStreamReader(f));
}
String next() {
while (st == null || !st.hasMoreTokens()) {
try {
st = new StringTokenizer(br.readLine());
} catch (IOException e) {
e.printStackTrace();
}
}
return st.nextToken();
}
String nextLine(){
String str = "";
try {
str = br.readLine();
} catch (IOException e) {
e.printStackTrace();
}
return str;
}
int nextInt() {
return Integer.parseInt(next());
}
long nextLong() {
return Long.parseLong(next());
}
double nextDoulbe() {
return Double.parseDouble(next());
}
}
static FastScanner newInput() throws IOException {
if (System.getProperty("JUDGE") != null) {
return new FastScanner(new File("input.txt"));
} else {
return new FastScanner(System.in);
}
}
static PrintWriter newOutput() throws IOException {
if (System.getProperty("JUDGE") != null) {
return new PrintWriter("output.txt");
} else {
return new PrintWriter(System.out);
}
}
}
Это решение содержит 2 очереди:
1. main_q - хранит введенные числа.
2. min_q - хранит минимальные числа по определенным правилам, которые мы описали (появляются в функциях MainQ.enqueue(x), MainQ.dequeue(), MainQ.get_min()).
Вот код на Python. Очередь реализована с использованием списка.
Основная идея заключается в функциях MainQ.enqueue (x), MainQ.dequeue (), MainQ.get_min ().
Одним из ключевых предположений является то, что очистка очереди занимает o(0).
Тест предоставляется в конце.
import numbers
class EmptyQueueException(Exception):
pass
class BaseQ():
def __init__(self):
self.l = list()
def enqueue(self, x):
assert isinstance(x, numbers.Number)
self.l.append(x)
def dequeue(self):
return self.l.pop(0)
def peek_first(self):
return self.l[0]
def peek_last(self):
return self.l[len(self.l)-1]
def empty(self):
return self.l==None or len(self.l)==0
def clear(self):
self.l=[]
class MainQ(BaseQ):
def __init__(self, min_q):
super().__init__()
self.min_q = min_q
def enqueue(self, x):
super().enqueue(x)
if self.min_q.empty():
self.min_q.enqueue(x)
elif x > self.min_q.peek_last():
self.min_q.enqueue(x)
else: # x <= self.min_q.peek_last():
self.min_q.clear()
self.min_q.enqueue(x)
def dequeue(self):
if self.empty():
raise EmptyQueueException("Queue is empty")
x = super().dequeue()
if x == self.min_q.peek_first():
self.min_q.dequeue()
return x
def get_min(self):
if self.empty():
raise EmptyQueueException("Queue is empty, NO minimum")
return self.min_q.peek_first()
INPUT_NUMS = (("+", 5), ("+", 10), ("+", 3), ("+", 6), ("+", 1), ("+", 2), ("+", 4), ("+", -4), ("+", 100), ("+", -40),
("-",None), ("-",None), ("-",None), ("+",-400), ("+",90), ("-",None),
("-",None), ("-",None), ("-",None), ("-",None), ("-",None), ("-",None), ("-",None), ("-",None))
if __name__ == '__main__':
min_q = BaseQ()
main_q = MainQ(min_q)
try:
for operator, i in INPUT_NUMS:
if operator=="+":
main_q.enqueue(i)
print("Added {} ; Min is: {}".format(i,main_q.get_min()))
print("main_q = {}".format(main_q.l))
print("min_q = {}".format(main_q.min_q.l))
print("==========")
else:
x = main_q.dequeue()
print("Removed {} ; Min is: {}".format(x,main_q.get_min()))
print("main_q = {}".format(main_q.l))
print("min_q = {}".format(main_q.min_q.l))
print("==========")
except Exception as e:
print("exception: {}".format(e))
Результат вышеприведенного теста:
"C:\Program Files\Python35\python.exe" C:/dev/python/py3_pocs/proj1/priority_queue.py
Added 5 ; Min is: 5
main_q = [5]
min_q = [5]
==========
Added 10 ; Min is: 5
main_q = [5, 10]
min_q = [5, 10]
==========
Added 3 ; Min is: 3
main_q = [5, 10, 3]
min_q = [3]
==========
Added 6 ; Min is: 3
main_q = [5, 10, 3, 6]
min_q = [3, 6]
==========
Added 1 ; Min is: 1
main_q = [5, 10, 3, 6, 1]
min_q = [1]
==========
Added 2 ; Min is: 1
main_q = [5, 10, 3, 6, 1, 2]
min_q = [1, 2]
==========
Added 4 ; Min is: 1
main_q = [5, 10, 3, 6, 1, 2, 4]
min_q = [1, 2, 4]
==========
Added -4 ; Min is: -4
main_q = [5, 10, 3, 6, 1, 2, 4, -4]
min_q = [-4]
==========
Added 100 ; Min is: -4
main_q = [5, 10, 3, 6, 1, 2, 4, -4, 100]
min_q = [-4, 100]
==========
Added -40 ; Min is: -40
main_q = [5, 10, 3, 6, 1, 2, 4, -4, 100, -40]
min_q = [-40]
==========
Removed 5 ; Min is: -40
main_q = [10, 3, 6, 1, 2, 4, -4, 100, -40]
min_q = [-40]
==========
Removed 10 ; Min is: -40
main_q = [3, 6, 1, 2, 4, -4, 100, -40]
min_q = [-40]
==========
Removed 3 ; Min is: -40
main_q = [6, 1, 2, 4, -4, 100, -40]
min_q = [-40]
==========
Added -400 ; Min is: -400
main_q = [6, 1, 2, 4, -4, 100, -40, -400]
min_q = [-400]
==========
Added 90 ; Min is: -400
main_q = [6, 1, 2, 4, -4, 100, -40, -400, 90]
min_q = [-400, 90]
==========
Removed 6 ; Min is: -400
main_q = [1, 2, 4, -4, 100, -40, -400, 90]
min_q = [-400, 90]
==========
Removed 1 ; Min is: -400
main_q = [2, 4, -4, 100, -40, -400, 90]
min_q = [-400, 90]
==========
Removed 2 ; Min is: -400
main_q = [4, -4, 100, -40, -400, 90]
min_q = [-400, 90]
==========
Removed 4 ; Min is: -400
main_q = [-4, 100, -40, -400, 90]
min_q = [-400, 90]
==========
Removed -4 ; Min is: -400
main_q = [100, -40, -400, 90]
min_q = [-400, 90]
==========
Removed 100 ; Min is: -400
main_q = [-40, -400, 90]
min_q = [-400, 90]
==========
Removed -40 ; Min is: -400
main_q = [-400, 90]
min_q = [-400, 90]
==========
Removed -400 ; Min is: 90
main_q = [90]
min_q = [90]
==========
exception: Queue is empty, NO minimum
Process finished with exit code 0
Мы знаем, что push и pop являются операциями с постоянным временем [O(1), если быть точным].
Но когда мы думаем о get_min()[то есть, чтобы найти текущее минимальное число в очереди], как правило, первое, что приходит на ум, - это поиск по всей очереди каждый раз, когда делается запрос на минимальный элемент. Но это никогда не даст работу с постоянным временем, которая является главной целью проблемы.
Об этом обычно спрашивают очень часто в интервью, поэтому вы должны знать хитрость
Для этого нам нужно использовать еще две очереди, которые будут отслеживать минимальный элемент, и мы должны продолжать модифицировать эти 2 очереди, так как мы выполняем операции push и pop в очереди, чтобы минимальный элемент был получен за время O (1).,
Вот самоописательный код sudo, основанный на вышеупомянутом подходе.
Queue q, minq1, minq2;
isMinq1Current=true;
void push(int a)
{
q.push(a);
if(isMinq1Current)
{
if(minq1.empty) minq1.push(a);
else
{
while(!minq1.empty && minq1.top < =a) minq2.push(minq1.pop());
minq2.push(a);
while(!minq1.empty) minq1.pop();
isMinq1Current=false;
}
}
else
{
//mirror if(isMinq1Current) branch.
}
}
int pop()
{
int a = q.pop();
if(isMinq1Current)
{
if(a==minq1.top) minq1.pop();
}
else
{
//mirror if(isMinq1Current) branch.
}
return a;
}
#include <iostream>
#include <queue>
#include <deque>
using namespace std;
queue<int> main_queue;
deque<int> min_queue;
void clearQueue(deque<int> &q)
{
while(q.empty() == false) q.pop_front();
}
void PushRear(int elem)
{
main_queue.push(elem);
if(min_queue.empty() == false && elem < min_queue.front())
{
clearQueue(min_queue);
}
while(min_queue.empty() == false && elem < min_queue.back())
{
min_queue.pop_back();
}
min_queue.push_back(elem);
}
void PopFront()
{
int elem = main_queue.front();
main_queue.pop();
if (elem == min_queue.front())
{
min_queue.pop_front();
}
}
int GetMin()
{
return min_queue.front();
}
int main()
{
PushRear(1);
PushRear(-1);
PushRear(2);
cout<<GetMin()<<endl;
PopFront();
PopFront();
cout<<GetMin()<<endl;
return 0;
}