在 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(n 2 )。
该问题的更好解决方案是使用元素的堆栈和索引。
我们将数组中当前元素的下一个较大和较小元素的索引存储在两个名为 nextGreater[] 和 nextSmaller[] 的数组中。这意味着数组 nextGreater 将存储当前元素的下一个更大元素的索引。例如 nextGreater[i] 将具有下一个更大元素的索引，即 arr[nextGreater[i]]。nextSmaller[] 也是如此。
因此，要访问数组的下一个较大元素的下一个最小元素。我们将在 nextGreater[i] 处找到下一个较小的索引元素。这将给出我们所需元素的索引，即所需元素是 arr[nextSmaller[nextGreater[i]]]。
为了找到元素，我们将使用堆栈数据结构来存储剩余子数组的元素。以下是该函数查找更大元素的方式。
=> 我们将从最后一次遍历数组，i -> n-1 到 0。
=> 如果栈不为空且栈顶小于当前元素 -> pop S，执行此操作直到找到更大的元素或栈为空。
=> 如果堆栈为空 -> 没有更大的元素可能，存储 -1，nextGreater[i] = -1。
=> else -> 下一个更大的元素在栈顶，存储栈顶， 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<<"数组的所有下一个较小的下一个较大的元素是 ";
findNextSmallerofNextGreaterElemenetArray(arr, n);
return 0;
}
数组的所有下一个较小的下一个较大的元素是 3 3 1 1 -1 -1
以上是 在 C++ 中的数组中查找下一个较小的下一个较大的 的全部内容， 来源链接： utcz.com/z/335600.html
