数据结构
网络
关系型数据库管理系统
操作系统
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 次查看
