資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究在 C++ 中查詢陣列中下一個較大數的下一個較小數
在這個問題中，我們給定一個包含 n 個整數值的陣列 arr[]。我們的任務是在陣列中查詢下一個較大數的下一個較小數。
問題描述 − 我們將找到陣列中大於當前元素的元素，然後我們將找到陣列中小於這個較大元素的元素。如果陣列中不存在下一個較小數或下一個較大數，則返回 -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(n2)。
更好的解決方案可以使用棧和元素的索引來解決該問題。
我們將在兩個名為 nextGreater[] 和 nextSmaller[] 的陣列中儲存當前元素的下一個較大元素和較小元素的索引。這意味著陣列 nextGreater 將儲存當前元素的下一個較大元素的索引。例如，nextGreater[i] 將包含下一個較大元素的索引，該元素將是 arr[nextGreater[i]]。nextSmaller[] 也將相同。
因此，要訪問陣列的下一個較大元素的下一個較小元素。我們將找到 nextGreater[i] 處的索引的下一個較小元素。這將給出我們所需元素的索引，即所需元素是 arr[nextSmaller[nextGreater[i]]]。
為了找到元素，我們將使用棧資料結構，它將儲存剩餘子陣列的元素。以下是查詢較大元素的功能工作原理。
=> 我們將從最後遍歷陣列，i -> n-1 到 0。
=> 如果棧不為空且棧頂小於當前元素 -> 彈出 S，繼續執行此操作，直到找到一個更大的元素或棧為空。
=> 如果棧為空 -> 沒有更大的元素可能，儲存 -1，nextGreater[i] = -1。
=> 否則 -> 下一個較大元素位於棧頂，儲存棧頂，nextGreater[i] = stack.top()。
=> 將當前元素推入棧中，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
285 次檢視
