Агуулгыг алгасах

Минимум стек / Минимум дараалал

Энэ өгүүлэлд бид гурван бодлого авч үзнэ: эхлээд бид стекийн хамгийн бага элементийг $O(1)$-д олох боломж олгодог байдлаар стекийг өөрчилнө, дараа нь дараалалтай ижлийг хийж, эцэст нь эдгээр өгөгдлийн бүтцийг ашиглан массив дахь тогтмол урттай бүх дэд хэрчмийн минимумыг $O(n)$-д олно.

Стекийг өөрчлөх

Бид стекээс элемент нэмэх, устгах ижил асимптот зан төлөвийг хадгалангаа стек дэх хамгийн бага элементийг $O(1)$ хугацаанд олох боломжтой байхаар стек өгөгдлийн бүтцийг өөрчлөхийг хүсэж байна. Түргэн сануулга, стек дээр бид зөвхөн нэг үзүүрт элемент нэмж, устгадаг.

Үүний тулд бид зөвхөн элементүүдийг стект хадгалахаас гадна тэдгээрийг хосоор нь хадгална: элемент өөрөө, ба энэ элементээс доош эхлэх стек дэх минимум.

stack<pair<int, int>> st;

Бүхэл стек дэх минимумыг олох нь зөвхөн stack.top().second утгыг харахаас тогтоно гэдэг нь тодорхой.

Стект шинэ элемент нэмэх буюу устгахыг тогтмол хугацаанд хийж болох нь мөн ойлгомжтой.

Хэрэгжүүлэлт:

  • Элемент нэмэх: 

    int new_min = st.empty() ? new_elem : min(new_elem, st.top().second);
st.push({new_elem, new_min});

  • Элемент устгах: 

    int removed_element = st.top().first;
st.pop();

  • Минимум олох: 

    int minimum = st.top().second;

Дарааллыг өөрчлөх (1-р арга)

Одоо бид дараалалтай ижил үйлдлүүдэд хүрэхийг хүсэж байна, өөрөөр хэлбэл бид төгсгөлд нь элемент нэмж, урдаас нь устгахыг хүсэж байна.

Энд бид дараалал өөрчлөх энгийн аргыг авч үзнэ. Гэвч энэ нь том сул талтай, учир нь өөрчилсөн дараалал үнэндээ бүх элементийг хадгалахгүй.

Гол санаа нь дараалалд зөвхөн минимумыг тодорхойлоход шаардлагатай зүйлсийг л хадгалах явдал юм. Тодруулбал бид дарааллыг буурахгүй дарааллаар хадгална (өөрөөр хэлбэл хамгийн бага утгыг толгойд хадгална), мэдээж дурын байдлаар биш, жинхэнэ минимум үргэлж дараалалд агуулагдах ёстой. Ингэснээр хамгийн бага элемент үргэлж дарааллын толгойд байна. Дараалалд шинэ элемент нэмэхээс өмнө "зүсэлт" хийхэд хангалттай: бид дараалын шинэ элементээс том сүүлийн бүх элементийг устгаж, дараа нь дараалалд шинэ элемент нэмнэ. Ингэснээр бид дарааллын дарааллыг эвдэхгүй бөгөөд мөн одоогийн элемент дараагийн ямар нэг алхамд минимум болвол түүнийг алдахгүй. Бидний устгасан бүх элемент өөрөө хэзээ ч минимум байж чадахгүй тул энэ үйлдэл зөвшөөрөгдөнө. Бид толгойноос элемент гаргаж авахыг хүсэх үед энэ нь үнэндээ тэнд байхгүй байж болно (учир нь бид өмнө нь бага элемент нэмэхдээ түүнийг устгасан). Тиймээс дараалалаас элемент устгахдаа бид элементийн утгыг мэдэх хэрэгтэй. Хэрэв дарааллын толгой ижил утгатай бол бид түүнийг аюулгүйгээр устгаж болно, эс бөгөөс бид юу ч хийхгүй.

Дээрх үйлдлүүдийн хэрэгжүүлэлтийг авч үзье:

deque<int> q;

  • Минимум олох: 

    int minimum = q.front();

  • Элемент нэмэх: 

    while (!q.empty() && q.back() > new_element)
    q.pop_back();
q.push_back(new_element);

  • Элемент устгах: 

    if (!q.empty() && q.front() == remove_element)
    q.pop_front();

Дунджаар эдгээр бүх үйлдэл зөвхөн $O(1)$ хугацаа авдаг нь тодорхой (учир нь элемент бүрийг зөвхөн нэг удаа нэмж, нэг удаа гаргаж болно).

Дарааллыг өөрчлөх (2-р арга)

Энэ бол 1-р аргын өөрчлөлт юм. Бид аль элементийг устгах ёстойгоо мэдэлгүйгээр элемент устгах боломжтой байхыг хүсэж байна. Үүнийг бид дараалал дахь элемент бүрийн индексийг хадгалснаар хийж чадна. Мөн бид аль хэдийн хэдэн элемент нэмж, устгасныг санана.

deque<pair<int, int>> q;
int cnt_added = 0;
int cnt_removed = 0;

  • Минимум олох: 

    int minimum = q.front().first;

  • Элемент нэмэх: 

    while (!q.empty() && q.back().first > new_element)
    q.pop_back();
q.push_back({new_element, cnt_added});
cnt_added++;

  • Элемент устгах: 

    if (!q.empty() && q.front().second == cnt_removed) 
    q.pop_front();
cnt_removed++;

Дарааллыг өөрчлөх (3-р арга)

Энд бид минимумыг $O(1)$-д олохын тулд дараалал өөрчлөх өөр аргыг авч үзнэ. Энэ арга нь хэрэгжүүлэхэд арай төвөгтэй боловч энэ удаад бид үнэндээ бүх элементийг хадгална. Мөн бид элементийн утгыг мэдэлгүйгээр урдаас нь устгаж болно.

Санаа нь бодлогыг бидний аль хэдийн бодсон стекийн бодлогод бууруулах явдал юм. Тиймээс бид зөвхөн хоёр стек ашиглан дарааллыг хэрхэн загварчлахыг сурах хэрэгтэй.

Бид s1 ба s2 гэсэн хоёр стек хийнэ. Мэдээж эдгээр стек нь өөрчилсөн хэлбэртэй байх ба ингэснээр бид минимумыг $O(1)$-д олж чадна. Бид s1 стект шинэ элемент нэмж, s2 стекээс элемент устгана. Хэрэв ямар нэг үед s2 стек хоосон бол бид бүх элементийг s1-ээс s2 руу зөөнө (энэ нь үндсэндээ тэдгээр элементийн дарааллыг эсрэг болгоно). Эцэст нь дараалал дахь минимумыг олох нь зүгээр л хоёр стекийн минимумыг олоход оршино.

Тиймээс бид бүх үйлдлийг дунджаар $O(1)$-д гүйцэтгэнэ (элемент бүрийг нэг удаа s1 стект нэмэх, нэг удаа s2 руу шилжүүлэх, нэг удаа s2-оос гаргана)

Хэрэгжүүлэлт:

stack<pair<int, int>> s1, s2;

  • Минимум олох: 

    if (s1.empty() || s2.empty()) 
    minimum = s1.empty() ? s2.top().second : s1.top().second;
else
    minimum = min(s1.top().second, s2.top().second);

  • Элемент нэмэх: 

    int minimum = s1.empty() ? new_element : min(new_element, s1.top().second);
s1.push({new_element, minimum});

  • Элемент устгах: 

    if (s2.empty()) {
    while (!s1.empty()) {
        int element = s1.top().first;
        s1.pop();
        int minimum = s2.empty() ? element : min(element, s2.top().second);
        s2.push({element, minimum});
    }
}
int remove_element = s2.top().first;
s2.pop();

Тогтмол урттай бүх дэд хэрчмийн минимумыг олох

$N$ урттай $A$ массив ба өгөгдсөн $M \le N$ өгөгдсөн гэж бодъё. Бид энэ массив дахь $M$ урттай дэд хэрчим бүрийн минимумыг олох ёстой, өөрөөр хэлбэл бид дараахыг олох ёстой:

$$\min_{0 \le i \le M-1} A[i], \min_{1 \le i \le M} A[i], \min_{2 \le i \le M+1} A[i],~\dots~, \min_{N-M \le i \le N-1} A[i]$$

Бид энэ бодлогыг шугаман хугацаанд буюу $O(n)$-д бодох ёстой.

Бид бодлогыг бодоход гурван өөрчилсөн дарааллын аль нэгийг ашиглаж болно. Шийдэл нь тодорхой байх ёстой: бид массивын эхний $M$ элементийг нэмж, түүний минимумыг олж гаргаад, дараа нь дараагийн элементийг дараалалд нэмж, массивын эхний элементийг устгаж, түүний минимумыг олж гаргах гэх мэт. Дараалалтай хийх бүх үйлдэл дунджаар тогтмол хугацаанд гүйцэтгэгддэг тул бүхэл алгоритмын complexity нь $O(n)$ болно.

Дасгал бодлогууд