k урттай гулсдаг цонх бүрийн хамгийн бага тоог deque ашиглан O(n) хугацаанд олно.

IntermediateХугацаа: O(n)Санах ой: O(k)
HackerRank дээр бодох

Эхлээд жижиг бодлого

a = [5, 2, 7, 6, 1, 8, 4, 3], k = 3. Гурван урттай цонх бүрийн хамгийн бага тоог ол.

5, 2, 7 → 2, 2, 7, 6 → 2, 7, 6, 1 → 1 гэх мэт. Хариу: 2 2 1 1 1 3.

Энгийн аргаас санаа руу

Энгийн арга: цонх бүрийн k тоог шалгана. O(n · k). n = 10⁵, k = 5 · 10⁴ бол 2.5 тэрбум алхам.

Гол санаа: цонхонд байгаа зарим тоо хэзээ ч хариу болохгүй. j < i, a[j] ≥ a[i] бол a[j] цонхноос эрт гарна, бас a[i]-гаас бага биш. Тиймээс түүнийг шууд хаяна. Үлдсэн index-үүдийг deque-д утга нь өсөх дарааллаар хадгална. Хамгийн бага нь үргэлж урд талд байна.

Нэр томьёо ба тэмдэглэгээ

dq
Index хадгалах deque. Урдаас ард утга нь өсөх дараалалтай.
pop_back
Ардаас гаргах: шинэ тооноос бага биш тоонуудыг хаяна.
pop_front
Урдаас гаргах: цонхноос гарсан index-ийг хаяна.
цонх
a[i - k + 1..i] хэсэг. i ≥ k − 1 үед бүрэн болно.
a
5
0
2
1
7
2
6
3
1
4
8
5
4
6
3
7
min
·
0
·
1
·
2
·
3
·
4
·
5
·
6
·
7
dq (утгууд нь)
хоосон

Array: 5 2 7 6 1 8 4 3. 3 урттай цонхыг баруун тийш гулсуулж, цонх бүрийн хамгийн бага тоог олъё. Deque-ийн урд талд үргэлж хамгийн бага нь байна.

Алхам 1 / 22
Хурд
  • Шинэ тоо a[i]
  • Deque дотор байгаа
  • Цонхонд байгаа
  • Гаргасан
  • Цонхноос гарсан
  • Цонхны хамгийн бага
Слайд 1 / 6

Гулсдаг цонх

k урттай цонх array дээгүүр гулсана. Цонх бүрийн хамгийн бага тоог олох хэрэгтэй. Цонх бүрт k тоог дахин харвал удаан. Deque дараагийн хариуг бэлэн барьж явна.

min-queue.cpp
#include <bits/stdc++.h>
using namespace std;
int n, k, a[100005];
deque<int> dq;
int main() {
cin >> n >> k;
for (int i = 0; i < n; i++) cin >> a[i];
for (int i = 0; i < n; i++) {
while (!dq.empty() && a[dq.back()] >= a[i]) {
dq.pop_back();
}
dq.push_back(i);
if (dq.front() <= i - k) {
dq.pop_front();
}
if (i >= k - 1) {
cout << a[dq.front()] << ' ';
}
}
cout << '\n';
return 0;
}

Юунд хэрэгтэй вэ?

Цонх гулсах бүрт хамгийн бага (эсвэл хамгийн их) тоог дахин хайлгүйгээр мэднэ. Queue-д тоо нэмж, гаргахын зэрэгцээ доторх хамгийн бага тоог шууд хэлдэг Min Queue ч энэ санаан дээр тулгуурладаг.

Яаж ажилладаг вэ?

1. Deque-д index-үүд хадгалагдана. Урдаас ард тэдний утга өсөх дарааллаар байна. 2. Шинэ a[i] ирэхэд ард байгаа тоо a[i]-гаас бага биш л бол ардаас гаргана. Тэд хэзээ ч хариу болохгүй: a[i] илүү бага бөгөөд цонхонд илүү удаан үлдэнэ. 3. i-г deque-ийн ард нэмнэ. 4. Урд байгаа index i − k-гаас хэтрэхгүй бол цонхноос гарсан байна. Түүнийг урдаас гаргана. 5. Цонх бүрэн болсон үед (i ≥ k − 1) хариу нь урд байгаа тоо. Оролт: эхний мөрөнд n ба k, дараагийн мөрөнд n тоо.

Яагаад зөв, хэр хурдан бэ?

Deque-д байгаа тоо бүр цонхонд байгаа бөгөөд түүнээс хойш ирсэн бүх тооноос хатуу бага. Тиймээс урд байгаа нь цонхны хамгийн бага. Хаясан тоо бүрийн оронд түүнээс бага буюу тэнцүү, цонхонд удаан үлдэх тоо байгаа тул хариу алдагдахгүй.

Index бүр deque-д нэг удаа орж, нэг удаа гарна. k хичнээн том байсан ч нийт O(n). n = 10⁶ бол 2 сая орчим алхам.

Түгээмэл алдаа

  • Утгыг хадгалах. Цонхноос гарсан эсэхийг шалгахад index хэрэгтэй.
  • dq.front() <= i - k нөхцөлийг < гэж бичих. Тэгвэл цонх k + 1 урттай болно.
  • Хариуг i >= k - 1 болохоос өмнө хэвлэх. Эхний k − 1 алхамд цонх бүрэн биш.
  • Хамгийн их тоо хэрэгтэй бол харьцуулалтыг <= болгоно. Тэмдгийг солихоо мартах.

Хязгаарын тохиолдол

  • k = 1: цонх бүр ганц тоо, хариу нь array өөрөө.
  • k = n: ганц цонх, хариу нь бүх array-н хамгийн бага.
  • Өсөх array: ардаас юу ч гарахгүй, зөвхөн урдаас гарна.
  • Буурах array: шинэ тоо бүр өмнөхийг ардаас гаргана, deque-д үргэлж ганц index.

Өөрийгөө шалга

  1. a = [4, 2, 12, 3], k = 2 бол хариу юу вэ?

    Хариу харах

    2 2 3.

  2. Яагаад шинэ тооноос бага биш тоог ардаас хаяж болдог вэ?

    Хариу харах

    Шинэ тоо түүнээс бага буюу тэнцүү бөгөөд цонхонд илүү удаан үлдэнэ. Хуучин тоо хэзээ ч ганцаараа хамгийн бага болохгүй.

Гурван дадлага

Hint-ээ нээхээс өмнө өөрөө оролдоорой.

  1. 1.a = [1, 3, 2, 5, 4], k = 2 дээр алхам бүрийн deque-г утгаар нь бич.

    Hint харах

    Ардаас гаргах, ард нэмэх, урдаас гаргах дарааллаар.

    Хариу ба тайлбар

    [1], [1, 3] → 1, [2] → 2, [2, 5] → 2, [4] → 4. Хариу: 1 2 2 4.

  2. 2.Цонх бүрийн хамгийн их тоог ол.

    Hint харах

    Deque-г утга нь буурах дараалалтай болго.

    Хариу ба тайлбар

    a[dq.back()] >= a[i] нөхцөлийг a[dq.back()] <= a[i] болгоно. Үлдсэн бүх код хэвээр.

  3. 3.Queue-д push(x), pop() үйлдэл ирнэ. Үйлдэл бүрийн дараа Queue доторх хамгийн бага тоог хэвлэ.

    Hint харах

    pop нь хамгийн эрт нэмэгдсэн тоог гаргадаг. Deque-ийн урд байгаа тоо мөн тэр байж болно.

    Хариу ба тайлбар

    Энгийн queue-тэй зэрэгцээ deque хадгална. push хийхэд deque-ийн ардаас x-ээс их тоонуудыг гаргаад x-ийг нэмнэ. pop хийхэд гарах тоо deque-ийн урд байгаа бол түүнийг ч гаргана. Хамгийн бага нь deque-ийн урд байна.

Жишээ

Оролт

8 3
5 2 7 6 1 8 4 3

Гаралт

2 2 1 1 1 3

Одоо өөрөө бодоод үз

Бодлого

Хичээл

Энэ сэдвийн хичээл удахгүй нэмэгдэнэ.