คำสั่งเพิ่ม ลบ และหาความต่าง Max-Min ใน C++

ภาพรวมปัญหา

ประมวลผล Q คำสั่ง 3 ประเภท:

• Type 1: เพิ่มตัวเลข N เข้ารายการ
• Type 2: ลบตัวเลข N ออกจากรายการ
• Type 3: คืนค่าความต่างระหว่างค่าสูงสุดและต่ำสุดในรายการ

ตัวอย่าง

Queries:
(1, 4) -> add 4
(1, 9) -> add 9
(1, 6) -> add 6
(2, 4) -> remove 4
(1, 3) -> add 3
(3)    -> max=9, min=3, diff=6
Output: 6

วิธีแก้ปัญหา

วิธีอาร์เรย์ธรรมดา - O(N) ต่อคำถาม Type 3

วนหา Max/Min ทุกครั้งที่ถาม

วิธี Set (Self-Balancing BST) - O(log N) ต่อการดำเนินการ

• ใช้ std::set เก็บข้อมูล (เรียงลำดับอัตโนมัติ ไม่ซ้ำ)
• Min = *set.begin()
• Max = *set.rbegin()
• Insert/Erase = O(log N)

ตัวอย่างโค้ด C++ (ใช้ Set)

#include <bits/stdc++.h>
using namespace std;

set myList;

void solveQuery(int type, int num) {
    if (type == 1) myList.insert(num);
    else if (type == 2) myList.erase(num);
    else if (type == 3) {
        int max = *myList.rbegin();
        int min = *myList.begin();
        cout << "Difference = " << (max - min);
    }
}

int main() {
    int Q = 6;
    int query[6][2] = {{1,5}, {1,9}, {1,6}, {2,4}, {1,3}, {3,0}};
    for (int i = 0; i < Q; i++)
        solveQuery(query[i][0], query[i][1]);
    return 0;
}

ผลลัพธ์

The difference between the maximum and minimum elements of the list is 6