Phần tử lớn hơn cả hai hàng xóm trong mảng (Peak Element) trong C++

Cho mảng arr[] n số nguyên dương. Tìm các phần tử **lớn hơn cả phần tử trước và phần tử sau nó** (các "đỉnh" cục bộ - Local Maxima/Peak Elements). Không xét phần tử đầu và cuối vì thiếu hàng xóm.

Ví dụ

Đầu vào: arr[] = {5, 4, 7, 1, 17, 8, 3}

Đầu ra: 7, 17

Giải thích:

• arr[2]=7 > arr[1]=4 và > arr[3]=1.
• arr[4]=17 > arr[3]=1 và > arr[5]=8.

Phương pháp giải

Duyệt mảng từ chỉ số 1 đến n-2. Kiểm tra điều kiện arr[i] > arr[i-1] && arr[i] > arr[i+1].

Độ phức tạp: O(N) thời gian, O(1) bộ nhớ.

Chương trình minh họa

#include <iostream>
#include <vector>
using namespace std;

vector<int> findPeakElements(int arr[], int n) {
    vector<int> peaks;
    for (int i = 1; i < n - 1; i++) {
        if (arr[i] > arr[i-1] && arr[i] > arr[i+1]) {
            peaks.push_back(arr[i]);
        }
    }
    return peaks;
}

int main() {
    int arr[] = {5, 4, 7, 1, 17, 8, 3};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    vector<int> peaks = findPeakElements(arr, n);
    cout << "Cac phan tu lon hon ca hai hang xom (Peak): ";
    for (int val : peaks) cout << val << " ";
    if (peaks.empty()) cout << "Khong co";
    return 0;
}

Đầu ra

Cac phan tu lon hon ca hai hang xom (Peak): 7 17 

Mở rộng: Nếu chỉ cần tìm **một** peak element bất kỳ, có thể dùng **Binary Search O(log N)**.