Hướng dẫn giải của Min Max Array

Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Đầu tiên, ta xây dựng mảng ~L_i~ là giá trị nhỏ nhất mà từ ~L_i~ tới ~i~ trong dãy, ~a_i~ chính bằng ~min~. Tương tự, ~R_i~ là giá trị lớn nhất mà từ ~i~ tới ~R_i~ trong dãy, ~a_i~ bằng ~min~. Hai mảng này có thể dễ dàng xây dựng được bằng ~stack~.

Tiếp theo, ta gọi mảng ~res_i~ có ý nghĩa là kết quả cho đoạn con có độ dài bằng ~i~. Mảng ~res_i~ sẽ được tính từ hai thao tác sau:

~res_i = max (res_i,a_j)~, với mọi ~j~ thỏa mãn ~R_j-L_j+1 = i~.
~res_i = max (res_i,res_j)~, với mọi ~j > i~.

Code:

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5+5;
int a[N];
int n;
int l[N],r[N];
int res[N];
signed main () {
    cin >> n;
    for (int i=1; i<=n; i++) cin >> a[i];
    stack<int> st;
    st.push(0);
    for (int i=1; i<=n; i++) {
        while (st.size() && a[i] <= a[st.top()]) st.pop();
        l[i] = st.top()+1;
        st.push(i);
    }
    while (st.size()) st.pop();
    st.push(n+1);
    for (int i=n; i>=1; i--) {
        while (st.size() && a[i] <= a[st.top()]) st.pop();
        r[i] = st.top()-1;
        st.push(i);
    }
    for (int i=1; i<=n; i++) {
        int len = r[i] - l[i] + 1;
        res[len] = max (res[len],a[i]);
    } 
    for (int i=n-1; i>=1; i--) res[i] = max (res[i],res[i+1]);
    for (int i=1; i<=n; i++) cout << res[i] << ' ';
}