# 算法设计：与输入顺序相同的下一个更大的元素

2021年3月17日15:13:34 发表评论 345 次浏览

## 推荐：请尝试以下方法{IDE}首先, 在继续解决方案之前。

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

## C#

``````// 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``````

``````11 -- 13
13 -- 21
21 -- -1
3 -- -1``````

O(n)如果要以相反的顺序打印每个元素的下一个较大的部分, 则不需要多余的空间(首先是指最后一个元素, 然后是倒数第二个, 依此类推, 直到第一个元素)