Phần tử lớn hơn tiếp theo là phần tử đầu tiên là phần tử lớn hơn sau nó. Hãy xem một ví dụ.
arr =[4, 5, 3, 2, 1]
Phần tử lớn hơn tiếp theo cho 4 là 5 và phần tử lớn hơn tiếp theo cho các phần tử 3, 2, 1 là -1 vì không có phần tử nào lớn hơn sau chúng.
Thuật toán
-
Khởi tạo mảng với các số ngẫu nhiên.
-
Khởi tạo một ngăn xếp và một mảng.
-
Lặp lại từ cuối mảng.
-
Xóa các phần tử khỏi ngăn xếp cho đến khi nó trống và phần tử trên cùng nhỏ hơn hoặc bằng phần tử hiện tại.
-
Nếu ngăn xếp trống, thì không có phần tử lớn hơn tiếp theo. Vì vậy, hãy thêm -1 vào mảng kết quả.
-
Nếu ngăn xếp không trống, thì phần tử trên cùng là phần tử lớn hơn tiếp theo cho phần tử hiện tại. Thêm nó vào mảng kết quả.
-
Đẩy phần tử hiện tại vào ngăn xếp.
-
-
Lặp lại mảng kết quả và in từng phần tử cùng với phần tử lớn hơn tiếp theo của nó.
Thực hiện
Sau đây là cách thực hiện thuật toán trên trong C ++
#include <bits/stdc++.h>
using namespace std;
void nextGreaterElements(int arr[], int n) {
stack<int> s;
int result[n];
for (int i = n - 1; i >= 0; i--) {
while (!s.empty() && s.top() <= arr[i]) {
s.pop();
}
if (s.empty()) {
result[i] = -1;
}else {
result[i] = s.top();
}
s.push(arr[i]);
}
for (int i = 0; i < n; i++) {
cout << arr[i] << " -> " << result[i] << endl;
}
}
int main() {
int arr[] = { 1, 2, 3, 4, 5 };
int n = 5;
nextGreaterElements(arr, n);
return 0;
} Đầu ra
Nếu bạn chạy đoạn mã trên, thì bạn sẽ nhận được kết quả sau.
1 -> 2 2 -> 3 3 -> 4 4 -> 5 5 -> -1