在 C++ 中的数组中查找下一个较小的下一个较大的!

2023-06-16 13:07:02 172

在这个问题中，我们得到一个由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²)。

该问题的更好解决方案是使用元素的堆栈和索引。

我们将数组中当前元素的下一个较大和较小元素的索引存储在两个名为nextGreater[]和nextSmaller[]的数组中。这意味着数组nextGreater将存储当前元素的下一个更大元素的索引。例如nextGreater[i]将具有下一个更大元素的索引，即arr[nextGreater[i]]。nextSmaller[]也是如此。

因此，要访问数组的下一个较大元素的下一个最小元素。我们将在nextGreater[i]处找到下一个较小的索引元素。这将给出我们所需元素的索引，即所需元素是arr[nextSmaller[nextGreater[i]]]。

为了找到元素，我们将使用堆栈数据结构来存储剩余子数组的元素。以下是该函数查找更大元素的方式。

=>我们将从最后一次遍历数组，i->n-1到0。

=>如果栈不为空且栈顶小于当前元素->popS，执行此操作直到找到更大的元素或栈为空。

=>如果堆栈为空->没有更大的元素可能，存储-1，nextGreater[i]=-1。

=>else->下一个更大的元素在栈顶，存储栈顶，nextGreater[i]=。stack.top()

=>将当前元素压入堆栈，stack.push()

可以使用相同的方法为数组的当前元素查找下一个较小的元素。一旦我们找到了两者的索引。我们可以使用这些索引从数组中找到所需的元素。

程序来说明我们的解决方案的工作，

示例

#include
using namespace std;
void findNextGreater(int arr[], int n, int next[]) {
   stack 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 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<输出结果数组的所有下一个较小的下一个较大的元素是 3 3 1 1 -1 -1

在 C++ 中的数组中查找下一个较小的下一个较大的!

输入

解释

解决方法

示例

热门推荐

随机推荐