Trong bài toán này, chúng ta được cung cấp một mảng arr [] gồm n giá trị nguyên. Nhiệm vụ của chúng ta là Tìm Nhỏ hơn tiếp theo của Lớn hơn tiếp theo trong một mảng.
Mô tả sự cố - Chúng tôi sẽ tìm một phần tử lớn hơn phần tử hiện tại trong mảng và sau đó chúng tôi sẽ tìm phần tử trong mảng nhỏ hơn phần tử lớn hơn này. Và nếu không có phần tử lớn hơn hoặc nhỏ hơn tiếp theo tồn tại trong mảng, trả về -1.
Hãy lấy một ví dụ để hiểu vấn đề,
Đầu vào
arr[] = {4, 2, 8, 3, 9, 1} Đầu ra
{3, 3, 1, 1, -1, -1} Giải thích
Mảng gồm các phần tử lớn hơn tiếp theo:{8, 8, 9, 9, -1, -1} Vì 9 là phần tử lớn nhất của mảng và 1 là phần tử cuối cùng nên chúng không có phần tử lớn hơn tiếp theo.
Mảng các phần tử nhỏ hơn tiếp theo của các phần tử lớn hơn tiếp theo:{3, 3, 1, 1, -1, -1}
Phương pháp tiếp cận giải pháp
Một giải pháp đơn giản cho vấn đề là bằng cách lặp lại mảng và tách mảng,
-
Tìm phần tử lớn hơn tiếp theo từ mảng.
-
Tìm một phần tử nhỏ hơn phần tử lớn hơn này trong mảng còn lại.
Giải pháp này để thực hiện công việc của nó nhưng độ phức tạp về thời gian là theo thứ tự O (n 2 ).
Giải pháp tốt hơn vấn đề có thể là sử dụng ngăn xếp và chỉ mục của các phần tử.
Chúng ta sẽ lưu trữ chỉ số của phần tử lớn hơn và nhỏ hơn tiếp theo của currentelement trong mảng trong hai tên mảng nextGreater [] và nextSmaller []. Điều này có nghĩa là mảng nextGreater sẽ lưu trữ chỉ số của phần tử lớn hơn tiếp theo của phần tử hiện tại. Ví dụ nextGreater [i] sẽ có chỉ số của phần tử lớn hơn tiếp theo sẽ là arr [nextGreater [i]]. Và điều tương tự cũng sẽ xảy ra với nextSmaller [].
Vì vậy, để truy cập phần tử nhỏ nhất tiếp theo của phần tử lớn hơn tiếp theo của mảng. Chúng ta sẽ tìm phần tử nhỏ hơn tiếp theo của chỉ mục tại nextGreater [i]. Điều này sẽ cung cấp chỉ mục của phần tử bắt buộc của chúng tôi, tức là phần tử bắt buộc là arr [nextSmaller [nextGreater [i]]].
Để tìm phần tử, chúng ta sẽ sử dụng cấu trúc dữ liệu ngăn xếp để lưu trữ các phần tử của mảng con còn lại. Đây là cách hàm sẽ hoạt động để tìm các phần tử lớn hơn.
-
=> Chúng ta sẽ duyệt qua mảng từ cuối cùng, i -> n-1 đến 0.
-
=> Nếu ngăn xếp không trống và đỉnh của ngăn xếp nhỏ hơn hiện tại -> pop S, hãy làm điều này cho đến khi tìm thấy phần tử lớn hơn hoặc ngăn xếp trống.
-
=> Nếu ngăn xếp trống -> không thể có phần tử lớn hơn, lưu trữ -1, nextGreater [i] =-1.
-
=> else -> phần tử lớn hơn tiếp theo ở trên cùng của ngăn xếp, lưu trữ ở trên cùng của ngăn xếp, nextGreater [i] =stack.top ().
-
=> đẩy phần tử hiện tại vào ngăn xếp, stack.push ()
Phương pháp tương tự có thể được sử dụng để tìm phần tử nhỏ hơn tiếp theo cho phần tử hiện tại của mảng. Và một khi chúng tôi đã tìm thấy các chỉ mục của cả hai. Chúng ta có thể sử dụng các chỉ mục này để tìm phần tử bắt buộc từ mảng.
Chương trình minh họa hoạt động của giải pháp của chúng tôi,
Ví dụ
#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;
} Đầu ra
All next smaller of next greater elements of the array are 3 3 1 1 -1 -1