Tìm phần tử nhỏ hơn tiếp theo của phần tử lớn hơn tiếp theo trong mảng C++

Giới thiệu

Cho mảng arr[] n phần tử. Với mỗi phần tử, tìm phần tử lớn hơn đầu tiên bên phải (Next Greater), sau đó tìm phần tử nhỏ hơn đầu tiên bên phải của phần tử lớn hơn đó (Next Smaller of Next Greater).

Ví dụ minh họa

Đầu vào

arr[] = {4, 2, 8, 3, 9, 1}

Đầu ra

{3, 3, 1, 1, -1, -1}

Giải thích

Next Greater:     {8, 8, 9, 9, -1, -1}
Next Smaller of NG: {3, 3, 1, 1, -1, -1}

Phương pháp giải: Sử dụng Stack - O(N)

Tính trước mảng nextGreater[] và nextSmaller[] lưu chỉ số của phần tử lớn hơn/nhỏ hơn tiếp theo. Kết quả: arr[nextSmaller[nextGreater[i]]].

Chương trình minh họa

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

void findNextGreater(int arr[], int n, int next[]) {
    stack st;
    for (int i = n-1; i >= 0; i--) {
        while (!st.empty() && arr[st.top()] <= arr[i]) st.pop();
        next[i] = st.empty() ? -1 : st.top();
        st.push(i);
    }
}

void findNextSmaller(int arr[], int n, int next[]) {
    stack st;
    for (int i = n-1; i >= 0; i--) {
        while (!st.empty() && arr[st.top()] >= arr[i]) st.pop();
        next[i] = st.empty() ? -1 : st.top();
        st.push(i);
    }
}

void findNextSmallerOfNextGreater(int arr[], int n) {
    int nextGreater[n], nextSmaller[n];
    findNextGreater(arr, n, nextGreater);
    findNextSmaller(arr, n, nextSmaller);
    
    for (int i = 0; i < n; i++) {
        if (nextGreater[i] != -1 && nextSmaller[nextGreater[i]] != -1)
            cout << arr[nextSmaller[nextGreater[i]]] << "\t";
        else
            cout << "-1\t";
    }
}

int main() {
    int arr[] = {4, 2, 8, 3, 9, 1};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << "All next smaller of next greater elements: ";
    findNextSmallerOfNextGreater(arr, n);
    return 0;
}

Đầu ra

All next smaller of next greater elements are 3 3 1 1 -1 -1