Previous Greater Element ใน C++

ในปัญหานี้ เราได้รับอาร์เรย์ งานของเราคือคืนค่าองค์ประกอบที่มากที่สุดที่อยู่ก่อนหน้าองค์ประกอบปัจจุบันในอาร์เรย์ มิฉะนั้นพิมพ์ -1

ลองดูตัวอย่างเพื่อทำความเข้าใจปัญหา

Input: {6, 2, 7, 1, 5, 3}
Output: -1, 6, -1, 7, 7, 7

ในการแก้ปัญหานี้ วิธีแก้ปัญหาที่ง่ายและชัดเจนจะเป็นการใช้ nested loops ที่จะตรวจสอบองค์ประกอบที่มากกว่าในส่วนก่อนหน้าของอาร์เรย์

โปรแกรมแสดงการนำวิธีแก้ปัญหาของเราไปใช้

ตัวอย่างโค้ด (วิธีง่าย)

#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;
}

ผลลัพธ์

-1   6   -1   7   -1   12

วิธีแก้ปัญหาที่มีประสิทธิภาพมากกว่าสำหรับการแก้ปัญหาของเราคือการใช้โครงสร้างข้อมูล Stack และรักษาตัวเลขก่อนหน้าที่มากกว่าอยู่ที่ยอดของ stack

โปรแกรมแสดงการนำวิธีแก้ปัญหานี้ไปใช้

ตัวอย่างโค้ด (วิธี Stack)

#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;
}

ผลลัพธ์

-1   6   -1   7   -1   12