Tương tự bài trước, nhưng yêu cầu in kết quả theo đúng thứ tự mảng gốc (không theo thứ tự pop stack).
Thuật toán (duyệt ngược)
- Duyệt mảng từ phải sang trái.
- Stack lưu các ứng viên NGE.
- Với
arr[i]: pop stack cho đến khi top >arr[i]hoặc rỗng. - Nếu rỗng → NGE = -1, ngược lại NGE = top.
- Push
arr[i]vào stack. - Lưu NGE vào mảng kết quả, cuối cùng in theo thứ tự 0..n-1.
Triển khai C++
#include <bits/stdc++.h>
using namespace std;
void nextGreaterElementsOrder(int arr[], int n) {
stack st;
vector res(n);
for (int i = n - 1; i >= 0; i--) {
while (!st.empty() && st.top() <= arr[i]) st.pop();
res[i] = st.empty() ? -1 : st.top();
st.push(arr[i]);
}
for (int i = 0; i < n; i++)
cout << arr[i] << " -> " << res[i] << endl;
}
int main() {
int arr[] = {1, 2, 3, 4, 5};
nextGreaterElementsOrder(arr, 5);
return 0;
} Kết quả
1 -> 2 2 -> 3 3 -> 4 4 -> 5 5 -> -1