Тоо бүрийн баруун талд байгаа өөрөөсөө том эхний тоог ганц гүйлтээр олдог Stack арга.

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

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

a = [4, 7, 2, 1, 5, 3, 8, 6]. Тоо бүрийн баруун талд байгаа өөрөөсөө том эхний тоог ол.

4-ийн хариу 7, 7-гийн хариу 8, 2 ба 1-ийн хариу 5 гэх мэт. 8, 6-гийн баруун талд том тоо алга. Хариу: 7 8 5 5 8 8 -1 -1.

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

Энгийн арга: i бүрээс баруун тийш явж, анхны том тоог хайна. Буурах array дээр n²/2 алхам, n = 10⁵ бол 5 тэрбум.

Гол санаа: хариугаа олоогүй тоонуудыг Stack-д хадгална. Шинэ тоо ирэхэд Stack-ийн оройн тоо түүнээс бага л бол оройн тооны хариу олдсон тул гаргана. Stack доторх тоонууд доороос дээш үргэлж буурч байдаг. Тиймээс Monotonic Stack гэж нэрлэдэг.

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

st, k
Array ашиглан хийсэн Stack: st[0..k-1], орой нь st[k - 1]. Утгыг биш index-ийг хадгална.
ans[i]
a[i]-гаас баруун талд байгаа өөрөөсөө том эхний тоо. Байхгүй бол −1.
monotonic
Доороос дээш үргэлж буурах (тэнцүү байж болно) дараалал.
O(n) нийт
Нэг тоо олон тоог зэрэг гаргаж болох ч тоо бүр нийтдээ нэг л удаа гардаг.
a
4
0
7
1
2
2
1
3
5
4
3
5
8
6
6
7
ans
?
0
?
1
?
2
?
3
?
4
?
5
?
6
?
7
st (утгууд нь)
хоосон

Array: 4 7 2 1 5 3 8 6. Тоо бүрийн баруун талд байгаа өөрөөсөө том эхний тоог олъё. Stack-д өөрөөсөө том тоогоо хүлээж буй тоонууд зогсоно.

Алхам 1 / 16
Хурд
  • Шинэ тоо a[i]
  • Stack дотор хүлээж буй
  • Хариугаа олсон
  • Хариутай
  • Том тоо олдоогүй
Слайд 1 / 5

Хэн надаас өндөр вэ?

Хүүхдүүд эгнээнд зогсож байна. Хүн бүр баруун тийшээ хараад өөрөөсөө өндөр эхний хүнийг олно. Хүн бүрээс бүгдийг шалгавал удаан. Stack үүнийг ганц гүйлтээр хийдэг.

monotonic-stack.cpp
#include <bits/stdc++.h>
using namespace std;
int n, k, a[100005], ans[100005], st[100005];
int main() {
cin >> n;
for (int i = 0; i < n; i++) cin >> a[i];
for (int i = 0; i < n; i++) ans[i] = -1;
for (int i = 0; i < n; i++) {
while (k > 0 && a[st[k - 1]] < a[i]) {
ans[st[k - 1]] = a[i];
k--;
}
st[k++] = i;
}
for (int i = 0; i < n; i++) cout << ans[i] << ' ';
cout << '\n';
return 0;
}

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

"Миний баруун талд надаас том эхний тоо аль вэ?" гэсэн асуултад бүх тоонд O(n) хугацаанд хариулна. Хамгийн том тэгш өнцөгт, температурын бодлого, "харагдах барилга" зэрэг олон бодлогын гол санаа.

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

1. Хариугаа хараахан олоогүй тоонуудын index Stack-д хадгалагдана. Доороос дээш тэдний утга буурч байдаг. 2. Шинэ a[i] ирэхэд оройд байгаа тоо a[i]-гаас бага л бол түүний хариу нь a[i]. Хариуг нь бичээд Stack-ээс гаргана. 3. Ингэж зогссоны дараа a[i] өөрөө Stack-д орж, өөрөөсөө том тоог хүлээнэ. 4. Төгсгөлд үлдсэн тоонуудын баруун талд илүү том тоо байгаагүй тул хариу нь −1. Тоо бүр нэг удаа орж, нэг удаа гардаг тул нийт O(n). Оролт: эхний мөрөнд n, дараагийн мөрөнд n тоо.

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

Stack-д байгаа тоо бүрийн хувьд түүнээс хойш ирсэн тоонууд бүгд түүнээс бага буюу тэнцүү. Тиймээс түүнээс том эхний тоо ирэх мөчид түүнийг гаргаж хариуг бичих нь зөв. Төгсгөлд үлдсэн тоонуудад том тоо огт ирээгүй.

Тоо бүр Stack-д нэг удаа орж, хамгийн ихдээ нэг удаа гардаг. Хоёр давхар loop байгаа ч нийт 2n алхам: O(n). n = 10⁶ бол 2 сая орчим.

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

  • Утгыг хадгалах. Хариуг ans[st[k - 1]] гэж бичихэд index хэрэгтэй.
  • < ба <=-г холих. Хатуу том хэрэгтэй бол a[st[k - 1]] < a[i]. <= гэвэл тэнцүү тоо ч хариу болно.
  • Stack хоосон эсэхийг (k > 0) шалгахаа мартвал st[-1] уншина.
  • ans-ийг −1-ээр эхлүүлэхээ мартах. Тэгвэл Stack-д үлдсэн тоонуудын хариу 0 гарна.

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

  • Өсөх array: тоо бүр дараагийнхаараа шууд гарна. Хариу нь баруун хөрш, сүүлийнх нь −1.
  • Буурах array: хэн ч гарахгүй, бүх хариу −1.
  • Ижил тоонууд [3, 3, 3]: < ашигладаг тул тэнцүү тоо хариу болохгүй, бүгд −1.
  • n = 1: хариу −1.

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

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

    Хариу харах

    3 3 -1.

  2. Буурах array дээр төгсгөлд Stack-д хэдэн тоо үлдэх вэ?

    Хариу харах

    n. Нэг ч тоо гарахгүй.

  3. Нийт хамгийн ихдээ хэдэн удаа k-- хийгдэх вэ?

    Хариу харах

    n − 1 удаа. Сүүлийн тоо үргэлж Stack-д үлддэг.

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

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

  1. 1.a = [5, 3, 4, 1, 6] дээр алхам бүрийн дараах Stack-ийг бич.

    Hint харах

    Stack-д утгыг нь бичихэд хангалттай.

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

    [5], [5, 3], [5, 4], [5, 4, 1], [6]. Хариу: 6 4 6 6 -1.

  2. 2.Тоо бүрийн зүүн талд байгаа өөрөөсөө бага хамгийн ойрын тоог ол.

    Hint харах

    Зүүнээс баруун тийш явж, Stack-д өсөх дараалал хадгал.

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

    Шинэ a[i] ирэхэд оройн тоо a[i]-гаас бага биш л бол гаргана. Үлдсэн орой бол хариу, Stack хоосон бол −1. Дараа нь a[i]-г Stack-д хийнэ.

  3. 3.Histogram дахь хамгийн том тэгш өнцөгтийн талбайг ол. Багана бүрийн өргөн 1, өндөр h[i].

    Hint харах

    Багана бүрийн зүүн, баруун талд байгаа өөрөөсөө намхан хамгийн ойрын баганыг ол.

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

    Monotonic Stack ашиглан L[i], R[i]-г олно. Хариу нь бүх i-д h[i] * (R[i] - L[i] - 1) утгуудын хамгийн их нь. Нийт O(n).

Жишээ

Оролт

8
4 7 2 1 5 3 8 6

Гаралт

7 8 5 5 8 8 -1 -1

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

Бодлого

Хичээл

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