Phần tử lớn hơn tiếp theo (Next Greater Element) C++

Với mỗi phần tử, tìm phần tử đầu tiên bên phải lớn hơn nó. Không có → -1.

Ví dụ

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

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

• Duyệt trái → phải.
• Stack lưu phần tử chưa có NGE.
• Khi arr[i] > stack.top(): pop, gán NGE = arr[i].
• Push arr[i].
• Cuối: stack còn lại → NGE = -1.

Triển khai C++

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

void nextGreaterElements(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[] = {1, 2, 3, 4, 5};
    nextGreaterElements(arr, 5);
    return 0;
}

Kết quả

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