หา Next Smaller ของ Next Greater ในอาร์เรย์ด้วย C++

ภาพรวมปัญหา

ได้รับอาร์เรย์ arr[] ต้องหาสำหรับแต่ละองค์ประกอบ:

1. Next Greater Element (NGE) - องค์ประกอบแรกทางขวาที่มากกว่า
2. Next Smaller Element (NSE) ของ NGE นั้น - องค์ประกอบแรกทางขวาของ NGE ที่น้อยกว่า NGE

ถ้าไม่มีให้คืน -1

ตัวอย่าง

อินพุต

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

เอาต์พุต

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

คำอธิบาย

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

วิธีแก้ปัญหา

ใช้ Stack หา Index ของ NGE และ NSE แล้วรวมกัน

1. หา nextGreaterIndex[i] = index ของ NGE ของ arr[i]
2. หา nextSmallerIndex[i] = index ของ NSE ของ arr[i]
3. คำตอบสำหรับ i คือ arr[nextSmallerIndex[nextGreaterIndex[i]]]

โค้ดตัวอย่าง

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

void findNextGreater(int arr[], int n, int next[]) {
    stack<int> 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<int> 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 findNextSmallerofNextGreaterElementArray(int arr[], int n) {
    int nextGreaterIndex[n];
    int nextSmallerIndex[n];
    
    findNextGreater(arr, n, nextGreaterIndex);
    findNextSmaller(arr, n, nextSmallerIndex);
    
    for (int i = 0; i < n; i++) {
        if (nextGreaterIndex[i] != -1 && nextSmallerIndex[nextGreaterIndex[i]] != -1)
            cout << arr[nextSmallerIndex[nextGreaterIndex[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: ";
    findNextSmallerofNextGreaterElementArray(arr, n);
    return 0;
}

เอาต์พุต

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

สรุป

ใช้ Stack แบบ Monotonic Stack หา NGE และ NSE ใน O(N) แล้วรวม index เข้าด้วยกัน