Phần tử lớn hơn trước đó trong C++

Trong bài toán này, chúng ta được cho một mảng. Nhiệm vụ của chúng ta là trả về phần tử lớn nhất đứng trước phần tử hiện tại trong mảng, nếu không có thì in -1.

Hãy xem một ví dụ để hiểu bài toán:

Đầu vào: {6, 2, 7, 1, 5, 3}
Đầu ra: -1, 6, -1, 7, 7, 7

Để giải quyết bài toán này, một giải pháp dễ dàng và rõ ràng sẽ là sử dụng các vòng lặp lồng nhau kiểm tra phần tử lớn hơn trong phần đi trước của mảng.

Chương trình minh họa triển khai giải pháp của chúng ta:

Ví dụ

#include <iostream>
using namespace std;
void preceddingGreatestElement(int arr[], int n){
    cout << "-1\t";
    int i, j;
    for (i = 1; i < n; i++) {
        for (j = i-1; j >= 0; j--) {
            if (arr[i]<arr[j]) {
                cout<<arr[j]<< "\t";
                break;
            }
        }
        if (j == -1)
            cout << "-1\t";
    }
}
int main() {
    int arr[] = { 6, 2, 7, 1, 12, 5 };
    int n = sizeof(arr) / sizeof(arr[0]);
    preceddingGreatestElement(arr, n);
    return 0;
}

Kết quả

-1   6   -1   7   -1   12

Một giải pháp hiệu quả hơn để giải quyết bài toán của chúng ta là sử dụng cấu trúc dữ liệu stack. Và duy trì số lớn hơn đi trước ở đỉnh stack.

Chương trình minh họa triển khai giải pháp này:

Ví dụ

#include <bits/stdc++.h>
using namespace std;
void preceddingGreatestElement(int arr[], int n) {
    stack<int> elements;
    elements.push(arr[0]);
    cout << "-1\t";
    for (int i = 1; i < n; i++) {
        while (elements.empty() == false && elements.top() < arr[i])
            elements.pop();
        if(elements.empty())
            cout<<"-1\t";
        else
            cout<<elements.top()<<"\t";
        elements.push(arr[i]);
    }
}
int main() {
    int arr[] = { 6, 2, 7, 1, 12, 5 };
    int n = sizeof(arr) / sizeof(arr[0]);
    preceddingGreatestElement(arr, n);
    return 0;
}

Kết quả

-1   6   -1   7   -1   12