Поиск минимума в очереди C++

178

12 мая 2022, 08:20

Реализую поиск минимума в очереди, но столкнулся с проблемой, что на больших массивах слишком долго работает. Подскажите, пожалуйста, можно ли ускорить?

struct Node {
    int data = 0;
    Node* next = nullptr;
};
struct Queue {
    Node* head = nullptr;
    Node* tail = nullptr;
    int q_size = 0;
    bool is_empty() {
        return this->head == nullptr;
    }
    int min() {
        int min;
        Node* temp = this->head;
        min = temp->data;
        int help = this->q_size;
        while (help) {
            if (temp->data < min)
                min = temp->data;
            temp = temp->next;
            --help;
        }
        return min;
    }
};

Answer 1

Сделайте стек, хранящий пары элемент/минимум от дна до данного элемента

add(value) {
   curmin = min(curmin, value)
   stack.push(pair(value, curmin))
}
stackmin() {
   return stack.top().second
}

А теперь возьмите два таких стека и на их основе сделайте очередь:

queuemin() 
    return min(instack.stackmin(), outstack.stackmin())
add(value) {
   instack.add(value)  //min при этом обновляется
}
pop() {  
   if outstack пустой
      перекинуть в него всё из instack c помощью add (которая обновляет min)
   return outstack.pop()
}

Вот нашёл, где я это видел: Модификация стека и очереди для нахождения минимума за O (1)