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

本文概述

• 建议：在继续解决方案之前, 请先在{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}首先, 在继续解决方案之前。

我们已经讨论了解决方案这里不会打印相同的订单。在这里, 我们从最右边的元素遍历数组。

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

---