Phần tử nhỏ hơn tiếp theo (Next Smaller Element) C++

Với mỗi phần tử trong mảng, tìm phần tử đầu tiên bên phải nhỏ hơn nó. Nếu không có → -1.

Ví dụ

arr = [5, 4, 3, 2, 1]
Output: 5→4, 4→3, 3→2, 2→1, 1→-1

Thuật toán Stack (O(N))

• Duyệt mảng trái → phải.
• Stack lưu các phần tử chưa tìm thấy NSE.
• Khi arr[i] < stack.top(): pop và gán NSE = arr[i].
• Push arr[i] vào stack.
• Cuối cùng, phần tử còn trong stack → NSE = -1.

Triển khai C++

#include <bits/stdc++.h>
using namespace std;

void nextSmallerElements(int arr[], int n) {
    stack st;
    st.push(arr[0]);
    for (int i = 1; i < n; i++) {
        while (!st.empty() && st.top() > arr[i]) {
            cout << st.top() << " -> " << arr[i] << endl;
            st.pop();
        }
        st.push(arr[i]);
    }
    while (!st.empty()) {
        cout << st.top() << " -> -1" << endl;
        st.pop();
    }
}

int main() {
    int arr[] = {5, 4, 3, 2, 1};
    nextSmallerElements(arr, 5);
    return 0;
}

Kết quả

5 -> 4
4 -> 3
3 -> 2
2 -> 1
1 -> -1