算法设计（与输入顺序相同的下一个更大的元素） _数据结构

本文概述

建议：在继续解决方案之前, 请先在{IDE}上尝试使用你的方法。
C ++
Java
Python3
C#

给定一个数组, 为每个元素打印下一个更大元素(NGE)。元素x的下一个更大元素是数组x中右侧第一个更大的元素。对于没有更大元素的元素, 请将下一个更大元素视为-1。下一个更大的元素应按与输入数组相同的顺序打印。
例子：

输入：arr [] = [4, 5, 2, 25}输出：5 25 25 -1输入：arr [] = [4, 5, 2, 25, 10}输出：5 25 25 -1 -1

推荐：请尝试以下方法{IDE}首先, 在继续解决方案之前。我们已经讨论了解决方案这里不会打印相同的订单。在这里, 我们从最右边的元素遍历数组。

在这种方法中, 我们开始从最后一个元素(nth)迭代到第一个(1st)元素
好处是, 当我们到达某个索引时, 他的下一个更大的元素将已经在堆栈中, 并且可以在同一索引处直接获取此元素。
达到某个索引后, 我们将弹出堆栈, 直到从当前元素获得更大的元素, 并且该元素将成为当前元素的答案
如果在执行弹出操作时堆栈变空, 则答案为-1
然后, 我们将答案存储在当前索引的数组中。

下面是上述方法的实现：
C ++

// A Stack based C++ program to find next // greater element for all array elements // in same order as input. #include < bits/stdc++.h> using namespace std; /* prints element and NGE pair for all elements of arr[] of size n */ void printNGE( int arr[], int n) { stack< int > s; int arr1[n]; // iterating from n-1 to 0 for ( int i = n - 1; i > = 0; i--) { /*We will pop till we get the greater element on top or stack gets empty*/ while (!s.empty() & & s.top() < = arr[i]) s.pop(); /*if stack gots empty means there is no element on right which is greater than the current element. if not empty then the next greater element is on top of stack*/ if (s.empty()) arr1[i] = -1; else arr1[i] = s.top(); s.push(arr[i]); }for ( int i = 0; i < n; i++) cout < < arr[i] < < " ---> " < < arr1[i] < < endl; }/* Driver program to test above functions */ int main() { int arr[] = { 11, 13, 21, 3 }; int n = sizeof (arr) / sizeof (arr[0]); printNGE(arr, n); return 0; }

Java

// A Stack based Java program to find next // greater element for all array elements // in same order as input. import java.util.*; class GfG { /* prints element and NGE pair for all elements of arr[] of size n */ static void printNGE( int arr[], int n) { Stack< Integer> s = new Stack< Integer> (); int arr1[] = new int [n]; // iterating from n-1 to 0 for ( int i = n - 1 ; i > = 0 ; i--) { /*We will pop till we get the greater element on top or stack gets empty*/ while (!s.isEmpty() & & s.peek() < = arr[i]) s.pop(); /*if stack gots empty means there is no element on right which is greater than the current element. if not empty then the next greater element is on top of stack*/ if (s.empty()) arr1[i] = - 1 ; else arr1[i] = s.peek(); s.push(arr[i]); } for ( int i = 0 ; i < n; i++) System.out.println(arr[i] + " ---> " + arr1[i]); } /* Driver program to test above functions */ public static void main(String[] args) { int arr[] = { 11 , 13 , 21 , 3 }; int n = arr.length; printNGE(arr, n); } }

Python3

# A Stack based Python3 program to find next # greater element for all array elements # in same order as input.# prints element and NGE pair for all # elements of arr[] of size n def printNGE(arr, n):s = list ()arr1 = [ 0 for i in range (n)]# iterating from n-1 to 0 for i in range (n - 1 , - 1 , - 1 ): # We will pop till we get the greater # element on top or stack gets empty while ( len (s) > 0 and s[ - 1 ] < = arr[i]): s.pop()# if stack gots empty means there # is no element on right which is # greater than the current element. # if not empty then the next greater # element is on top of stack if ( len (s) = = 0 ): arr1[i] = - 1 else : arr1[i] = s[ - 1 ]s.append(arr[i])for i in range (n): print (arr[i], " ---> " , arr1[i] )# Driver Code arr = [ 11 , 13 , 21 , 3 ] n = len (arr) printNGE(arr, n)# This code is contributed by Mohit kumar 29

// A Stack based C# program to find next // greater element for all array elements // in same order as input. using System; using System.Collections.Generic; class GFG { /* prints element and NGE pair for all elements of arr[] of size n */ static void printNGE( int []arr, int n) { Stack< int > s = new Stack< int > (); int []arr1 = new int [n]; // iterating from n-1 to 0 for ( int i = n - 1; i > = 0; i--) { /*We will pop till we get the greater element on top or stack gets empty*/ while (s.Count != 0 & & s.Peek() < = arr[i]) s.Pop(); /*if stack gots empty means there is no element on right which is greater than the current element. if not empty then the next greater element is on top of stack*/ if (s.Count == 0) arr1[i] = -1; else arr1[i] = s.Peek(); s.Push(arr[i]); } for ( int i = 0; i < n; i++) Console.WriteLine(arr[i] + " ---> " + arr1[i]); } // Driver Code public static void Main(String[] args) { int []arr = { 11, 13, 21, 3 }; int n = arr.Length; printNGE(arr, n); } }// This code is contributed by Ajay Kumar

输出：