ในปัญหานี้ เราได้รับอาร์เรย์ arr[] ซึ่งประกอบด้วยค่าจำนวนเต็ม n ค่า งานของเราคือค้นหาสิ่งที่เล็กกว่าตัวถัดไปจาก Greater ตัวถัดไปในอาร์เรย์
คำอธิบายปัญหา − เราจะพบองค์ประกอบที่มากกว่าองค์ประกอบปัจจุบันในอาร์เรย์ จากนั้นเราจะพบองค์ประกอบในอาร์เรย์ที่เล็กกว่าองค์ประกอบที่ใหญ่กว่านี้ และหากไม่มีองค์ประกอบที่เล็กกว่าหรือสูงกว่าถัดไปในอาร์เรย์ ให้คืนค่า -1
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
อินพุต
arr[] = {4, 2, 8, 3, 9, 1} ผลลัพธ์
{3, 3, 1, 1, -1, -1} คำอธิบาย
อาร์เรย์ขององค์ประกอบที่มากกว่าถัดไป :{8, 8, 9, 9, -1, -1} เนื่องจาก 9 เป็นองค์ประกอบที่ใหญ่ที่สุดของอาร์เรย์ และ 1 เป็นองค์ประกอบสุดท้าย พวกมันจึงไม่มีองค์ประกอบที่ใหญ่กว่าถัดไป
อาร์เรย์ขององค์ประกอบที่ใหญ่กว่าถัดไป :{3, 3, 1, 1, -1, -1}
แนวทางการแก้ปัญหา
วิธีแก้ปัญหาอย่างง่ายคือการวนซ้ำบนอาร์เรย์และสำหรับแต่ละองค์ประกอบของอาร์เรย์
-
ค้นหาองค์ประกอบที่มากขึ้นถัดไปจากอาร์เรย์
-
ค้นหาองค์ประกอบที่เล็กกว่าองค์ประกอบที่ใหญ่กว่านี้ในอาร์เรย์ที่เหลือ
วิธีแก้ปัญหานี้เพื่อทำงาน แต่ความซับซ้อนของเวลาอยู่ในลำดับ O(n 2 )
ทางออกที่ดีกว่า ปัญหาสามารถใช้สแต็กและดัชนีขององค์ประกอบ
เราจะจัดเก็บดัชนีขององค์ประกอบที่มากขึ้นและเล็กถัดไปขององค์ประกอบปัจจุบันในอาร์เรย์ในชื่ออาร์เรย์สองชื่อ nextGreater[] และ nextSmaller[] ซึ่งหมายความว่าอาร์เรย์ nextGreater จะเก็บดัชนีขององค์ประกอบที่ใหญ่กว่าถัดไปขององค์ประกอบปัจจุบัน ตัวอย่างเช่น nextGreater[i] จะมีดัชนีขององค์ประกอบที่ใหญ่กว่าถัดไป ซึ่งจะเป็น arr[nextGreater[i]] และเช่นเดียวกันสำหรับ nextSmaller[] ด้วย
ดังนั้น เพื่อเข้าถึงองค์ประกอบที่เล็กที่สุดถัดไปขององค์ประกอบที่ใหญ่กว่าถัดไปของอาร์เรย์ เราจะพบองค์ประกอบเล็ก ๆ ของดัชนีต่อไปที่ nextGreater[i] สิ่งนี้จะให้ดัชนีขององค์ประกอบที่จำเป็นของเรา นั่นคือองค์ประกอบที่จำเป็นคือ arr[nextSmaller[nextGreater[i]]].
ในการค้นหาองค์ประกอบ เราจะใช้โครงสร้างข้อมูลสแต็ก ซึ่งจะเก็บองค์ประกอบของอาร์เรย์ย่อยที่เหลือ นี่คือการทำงานของฟังก์ชันเพื่อค้นหาองค์ประกอบที่มากขึ้น
-
=> เราจะสำรวจอาร์เรย์จากครั้งสุดท้าย i -> n-1 ถึง 0
-
=> หากสแต็กไม่ว่างเปล่าและด้านบนของสแต็กมีขนาดเล็กกว่าองค์ประกอบปัจจุบัน -> pop S ให้ทำสิ่งนี้จนกว่าจะพบองค์ประกอบที่มากกว่าหรือสแต็กว่างเปล่า
-
=> หาก stack ว่างเปล่า -> ไม่มีองค์ประกอบใดที่มากกว่านั้น ให้เก็บ -1,nextGreater[i] =-1
-
=> else -> องค์ประกอบที่ใหญ่กว่าถัดไปอยู่ที่ด้านบนสุดของ stack, เก็บด้านบนสุดของ stack, nextGreater[i] =stack.top()
-
=> ผลักองค์ประกอบปัจจุบันลงใน stack, stack.push()
วิธีเดียวกันนี้สามารถใช้เพื่อค้นหาองค์ประกอบที่เล็กกว่าถัดไปสำหรับองค์ประกอบปัจจุบันของอาร์เรย์ และเมื่อเราพบดัชนีของทั้งสองแล้ว เราสามารถใช้ดัชนีเหล่านี้เพื่อค้นหาองค์ประกอบที่จำเป็นจากอาร์เรย์ได้
โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา
ตัวอย่าง
#include<bits/stdc++.h>
using namespace std;
void findNextGreater(int arr[], int n, int next[]) {
stack<int> nextGreater;
int i = n-1;
while(i >= 0) {
while (!nextGreater.empty() && arr[nextGreater.top()] <= arr[i] )
nextGreater.pop();
if (!nextGreater.empty())
next[i] = nextGreater.top();
else
next[i] = -1;
nextGreater.push(i);
i--;
}
}
void findNextSmaller(int arr[], int n, int next[]) {
stack<int> nextSmaller;
int i = n-1 ;
while(i >= 0){
while (!nextSmaller.empty() && arr[nextSmaller.top()] >= arr[i])
nextSmaller.pop();
if (!nextSmaller.empty())
next[i] = nextSmaller.top();
else
next[i] = -1;
nextSmaller.push(i);
i -- ;
}
}
void findNextSmallerofNextGreaterElemenetArray(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 of the array are ";
findNextSmallerofNextGreaterElemenetArray(arr, n);
return 0;
} ผลลัพธ์
All next smaller of next greater elements of the array are 3 3 1 1 -1 -1
