Minimumli deque

Vazifa

Quyidagi amallarni qo‘llab-quvvatlaydigan dekni amalga oshirish:

push_front(x) — boshiga qo‘shish
push_back(x) — oxiriga qo‘shish
pop_front() — boshidan o‘chirish
pop_back() — oxiridan o‘chirish
get_min() — minimal elementni olish

G‘oya: ikki tuzilma (ikki MinStack) ushlab turamiz, lekin «navbatdagidek hammasini quyib yuborish» o‘rniga
biz qayta muvozanatlaymiz, qismlardan biri bo‘sh bo‘lib qolsa (o‘lchamlarni taxminan teng qilamiz).

G‘oya

Dekni ikki qism sifatida saqlaymiz:

L (left) — dekning boshiga yaqin elementlar (stekning tepasi = front)
R (right) — dekning oxiriga yaqin elementlar (stekning tepasi = back)

Shunda:

front L ning tepasida yotadi
back R ning tepasida yotadi
dek minimumi = min(L.min, R.min)

Agar bizga tomondan o‘chirish kerak bo‘lsa, lekin mos stek bo‘sh bo‘lsa:

barcha elementlarni to‘g‘ri tartibda yig‘amiz,
yarmiga bo‘lamiz,
L va R o‘lchamlari yaqin bo‘ladigan qilib qayta joylaymiz.

Amalga oshirish (C++)

struct MinStack { stack<int> st; stack<int> mn; void push(int x) { st.push(x); if (mn.empty()) mn.push(x); else mn.push(min(x, mn.top())); } int pop_value() { int x = st.top(); st.pop(); mn.pop(); return x; } int top() { return st.top(); } int get_min() { return mn.top(); } bool empty() { return st.empty(); } int size() { return (int)st.size(); } void clear() { while (!st.empty()) st.pop(); while (!mn.empty()) mn.pop(); } }; struct MinDeque { MinStack L; // front side MinStack R; // back side // dekning barcha elementlarini to‘g‘ri tartibda vektorga yig‘ish (front -> back) vector<int> dump_all() { vector<int> left_part; while (!L.empty()) { left_part.push_back(L.pop_value()); // allaqachon front -> ... tartibida } vector<int> right_reversed; while (!R.empty()) { right_reversed.push_back(R.pop_value()); // bu back -> ... } reverse(right_reversed.begin(), right_reversed.end()); // endi ... -> back vector<int> all; all.reserve(left_part.size() + right_reversed.size()); for (int x : left_part) all.push_back(x); for (int x : right_reversed) all.push_back(x); return all; } // L va R taxminan bir xil o‘lchamda bo‘lishi uchun qayta yig‘ish void rebalance() { vector<int> a = dump_all(); int n = (int)a.size(); if (n == 0) return; int left_cnt = (n + 1) / 2; // L R dan biroz katta yoki teng // L ni tiklaymiz: top(L) front = a[0] bo‘lishini xohlaymiz for (int i = left_cnt - 1; i >= 0; i--) { L.push(a[i]); } // R ni tiklaymiz: top(R) back = a[n-1] bo‘lishini xohlaymiz for (int i = left_cnt; i < n; i++) { R.push(a[i]); } } // boshiga qo‘shish void push_front(int x) { L.push(x); } // oxiriga qo‘shish void push_back(int x) { R.push(x); } // boshidan o‘chirish void pop_front() { if (L.empty()) { rebalance(); } L.pop_value(); } // oxiridan o‘chirish void pop_back() { if (R.empty()) { rebalance(); } R.pop_value(); } // minimum int get_min() { if (L.empty()) return R.get_min(); if (R.empty()) return L.get_min(); return min(L.get_min(), R.get_min()); } bool empty() { return L.empty() && R.empty(); } int size() { return L.size() + R.size(); } };