给定一个数组，为每个元素打印下一个较大元素（NGE）。元素x的下一个较大元素是数组中x右侧的第一个较大元素。没有更大元素的元素，考虑下一个更大的元素为-1。
null
例如：
- 对于数组，最右边的元素总是将下一个较大的元素作为-1。
- 对于按降序排序的数组，所有元素的下一个较大元素都为-1。
- 对于输入数组[4,5,2,25]，每个元素的下一个较大元素如下所示。
Element NGE 4 --> 5 5 --> 25 2 --> 25 25 --> -1
d） 对于输入数组[13,7,6,12}，每个元素的下一个较大元素如下所示。
Element NGE 13 --> -1 7 --> 12 6 --> 12 12 --> -1
方法1（简单） 使用两个循环：外部循环逐个拾取所有元素。内部循环为外部循环拾取的元素查找第一个较大的元素。如果找到较大的元素，则该元素将作为下一个元素打印，否则将打印-1。
以下是上述方法的实施情况：
C++
// Simple C++ program to print // next greater elements in a // given array #include<iostream> using namespace std; /* prints element and NGE pair for all elements of arr[] of size n */ void printNGE( int arr[], int n) { int next, i, j; for (i = 0; i < n; i++) { next = -1; for (j = i + 1; j < n; j++) { if (arr[i] < arr[j]) { next = arr[j]; break ; } } cout << arr[i] << " -- " << next << endl; } } // Driver Code int main() { int arr[] = {11, 13, 21, 3}; int n = sizeof (arr)/ sizeof (arr[0]); printNGE(arr, n); return 0; } // This code is contributed // by Akanksha Rai(Abby_akku) |
C
// Simple C program to print next greater elements // in a given array #include<stdio.h> /* prints element and NGE pair for all elements of arr[] of size n */ void printNGE( int arr[], int n) { int next, i, j; for (i=0; i<n; i++) { next = -1; for (j = i+1; j<n; j++) { if (arr[i] < arr[j]) { next = arr[j]; break ; } } printf ( "%d -- %dn" , arr[i], next); } } int main() { int arr[]= {11, 13, 21, 3}; int n = sizeof (arr)/ sizeof (arr[0]); printNGE(arr, n); return 0; } |
JAVA
// Simple Java program to print next // greater elements in a given array class Main { /* prints element and NGE pair for all elements of arr[] of size n */ static void printNGE( int arr[], int n) { int next, i, j; for (i= 0 ; i<n; i++) { next = - 1 ; for (j = i+ 1 ; j<n; j++) { if (arr[i] < arr[j]) { next = arr[j]; break ; } } System.out.println(arr[i]+ " -- " +next); } } public static void main(String args[]) { int arr[]= { 11 , 13 , 21 , 3 }; int n = arr.length; printNGE(arr, n); } } |
python
# Function to print element and NGE pair for all elements of list def printNGE(arr): for i in range ( 0 , len (arr), 1 ): next = - 1 for j in range (i + 1 , len (arr), 1 ): if arr[i] < arr[j]: next = arr[j] break print ( str (arr[i]) + " -- " + str ( next )) # Driver program to test above function arr = [ 11 , 13 , 21 , 3 ] printNGE(arr) # This code is contributed by Sunny Karira |
C#
// Simple C# program to print next // greater elements in a given array using System; class GFG { /* prints element and NGE pair for all elements of arr[] of size n */ static void printNGE( int []arr, int n) { int next, i, j; for (i = 0; i < n; i++) { next = -1; for (j = i + 1; j < n; j++) { if (arr[i] < arr[j]) { next = arr[j]; break ; } } Console.WriteLine(arr[i] + " -- " + next); } } // driver code public static void Main() { int []arr= {11, 13, 21, 3}; int n = arr.Length; printNGE(arr, n); } } // This code is contributed by Sam007 |
PHP
<?php // Simple PHP program to print next // greater elements in a given array /* prints element and NGE pair for all elements of arr[] of size n */ function printNGE( $arr , $n ) { for ( $i = 0; $i < $n ; $i ++) { $next = -1; for ( $j = $i + 1; $j < $n ; $j ++) { if ( $arr [ $i ] < $arr [ $j ]) { $next = $arr [ $j ]; break ; } } echo $arr [ $i ]. " -- " . $next . "" ; } } // Driver Code $arr = array (11, 13, 21, 3); $n = count ( $arr ); printNGE( $arr , $n ); // This code is contributed by Sam007 ?> |
Javascript
<script> // Simple JavaScript program to print // next greater elements in a // given array /* prints element and NGE pair for all elements of arr[] of size n */ function printNGE(arr, n) { var next, i, j; for (i = 0; i < n; i++) { next = -1; for (j = i + 1; j < n; j++) { if (arr[i] < arr[j]) { next = arr[j]; break ; } } document.write(arr[i] + " -- " + next); document.write( "<br>" ); } } // Driver Code var arr = [11, 13, 21, 3]; var n = arr.length; printNGE(arr, n); // This code is contributed by rdtank. </script> |
输出
11 -- 1313 -- 2121 -- -13 -- -1
时间复杂性： O（N） 2. ) 辅助空间： O（1）
方法2（使用堆栈）
- 将第一个元素推入堆栈。
- 一个接一个地选择其余的元素，并在循环中遵循以下步骤。
- 将当前元素标记为 下一个 .
- 如果堆栈不是空的，则将堆栈的顶部元素与 下一个 .
- 如果next大于top元素，则从堆栈中弹出元素。 下一个 是弹出元素的下一个较大元素。
- 当弹出的元素小于时，继续从堆栈弹出 下一个 . 下一个 成为所有此类弹出元素的下一个更大元素。
- 最后，按下堆栈中的下一个。
- 在步骤2中的循环结束后，从堆栈中弹出所有元素，并打印-1作为它们的下一个元素。
下图是上述方法的试运行：
![图片[1]-下一个更大的元素-yiteyi-C++库](https://media.geeksforgeeks.org/wp-content/cdn-uploads/20190626132057/NextGreaterElement.png)
以下是上述方法的实施情况：
C++
// A Stack based C++ program to find next // greater element for all array elements. #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; /* push the first element to stack */ s.push(arr[0]); // iterate for rest of the elements for ( int i = 1; i < n; i++) { if (s.empty()) { s.push(arr[i]); continue ; } /* if stack is not empty, then pop an element from stack. If the popped element is smaller than next, then a) print the pair b) keep popping while elements are smaller and stack is not empty */ while (s.empty() == false && s.top() < arr[i]) { cout << s.top() << " --> " << arr[i] << endl; s.pop(); } /* push next to stack so that we can find next greater for it */ s.push(arr[i]); } /* After iterating over the loop, the remaining elements in stack do not have the next greater element, so print -1 for them */ while (s.empty() == false ) { cout << s.top() << " --> " << -1 << endl; s.pop(); } } /* Driver code */ int main() { int arr[] = { 11, 13, 21, 3 }; int n = sizeof (arr) / sizeof (arr[0]); printNGE(arr, n); return 0; } |
C
// A Stack based C program to find next // greater element for all array elements. #include <stdbool.h> #include <stdio.h> #include <stdlib.h> #define STACKSIZE 100 // stack structure struct stack { int top; int items[STACKSIZE]; }; // Stack Functions to be used by printNGE() void push( struct stack* ps, int x) { if (ps->top == STACKSIZE - 1) { printf ( "Error: stack overflown" ); getchar (); exit (0); } else { ps->top += 1; int top = ps->top; ps->items[top] = x; } } bool isEmpty( struct stack* ps) { return (ps->top == -1) ? true : false ; } int pop( struct stack* ps) { int temp; if (ps->top == -1) { printf ( "Error: stack underflow n" ); getchar (); exit (0); } else { int top = ps->top; temp = ps->items[top]; ps->top -= 1; return temp; } } /* prints element and NGE pair for all elements of arr[] of size n */ void printNGE( int arr[], int n) { int i = 0; struct stack s; s.top = -1; int element, next; /* push the first element to stack */ push(&s, arr[0]); // iterate for rest of the elements for (i = 1; i < n; i++) { next = arr[i]; if (isEmpty(&s) == false ) { // if stack is not empty, then pop an element // from stack element = pop(&s); /* If the popped element is smaller than next, then a) print the pair b) keep popping while elements are smaller and stack is not empty */ while (element < next) { printf ( "n %d --> %d" , element, next); if (isEmpty(&s) == true ) break ; element = pop(&s); } /* If element is greater than next, then push the element back */ if (element > next) push(&s, element); } /* push next to stack so that we can find next greater for it */ push(&s, next); } /* After iterating over the loop, the remaining elements in stack do not have the next greater element, so print -1 for them */ while (isEmpty(&s) == false ) { element = pop(&s); next = -1; printf ( "n %d --> %d" , element, next); } } /* Driver code */ int main() { int arr[] = { 11, 13, 21, 3 }; int n = sizeof (arr) / sizeof (arr[0]); printNGE(arr, n); getchar (); return 0; } |
JAVA
// Java program to print next // greater element using stack public class NGE { static class stack { int top; int items[] = new int [ 100 ]; // Stack functions to be used by printNGE void push( int x) { if (top == 99 ) { System.out.println( "Stack full" ); } else { items[++top] = x; } } int pop() { if (top == - 1 ) { System.out.println( "Underflow error" ); return - 1 ; } else { int element = items[top]; top--; return element; } } boolean isEmpty() { return (top == - 1 ) ? true : false ; } } /* prints element and NGE pair for all elements of arr[] of size n */ static void printNGE( int arr[], int n) { int i = 0 ; stack s = new stack(); s.top = - 1 ; int element, next; /* push the first element to stack */ s.push(arr[ 0 ]); // iterate for rest of the elements for (i = 1 ; i < n; i++) { next = arr[i]; if (s.isEmpty() == false ) { // if stack is not empty, then // pop an element from stack element = s.pop(); /* If the popped element is smaller than next, then a) print the pair b) keep popping while elements are smaller and stack is not empty */ while (element < next) { System.out.println(element + " --> " + next); if (s.isEmpty() == true ) break ; element = s.pop(); } /* If element is greater than next, then push the element back */ if (element > next) s.push(element); } /* push next to stack so that we can find next greater for it */ s.push(next); } /* After iterating over the loop, the remaining elements in stack do not have the next greater element, so print -1 for them */ while (s.isEmpty() == false ) { element = s.pop(); next = - 1 ; System.out.println(element + " -- " + next); } } // Driver Code public static void main(String[] args) { int arr[] = { 11 , 13 , 21 , 3 }; int n = arr.length; printNGE(arr, n); } } // Thanks to Rishabh Mahrsee for contributing this code |
python
# Python program to print next greater element using stack # Stack Functions to be used by printNGE() def createStack(): stack = [] return stack def isEmpty(stack): return len (stack) = = 0 def push(stack, x): stack.append(x) def pop(stack): if isEmpty(stack): print ( "Error : stack underflow" ) else : return stack.pop() '''prints element and NGE pair for all elements of arr[] ''' def printNGE(arr): s = createStack() element = 0 next = 0 # push the first element to stack push(s, arr[ 0 ]) # iterate for rest of the elements for i in range ( 1 , len (arr), 1 ): next = arr[i] if isEmpty(s) = = False : # if stack is not empty, then pop an element from stack element = pop(s) '''If the popped element is smaller than next, then a) print the pair b) keep popping while elements are smaller and stack is not empty ''' while element < next : print ( str (element) + " -- " + str ( next )) if isEmpty(s) = = True : break element = pop(s) '''If element is greater than next, then push the element back ''' if element > next : push(s, element) '''push next to stack so that we can find next greater for it ''' push(s, next ) '''After iterating over the loop, the remaining elements in stack do not have the next greater element, so print -1 for them ''' while isEmpty(s) = = False : element = pop(s) next = - 1 print ( str (element) + " -- " + str ( next )) # Driver code arr = [ 11 , 13 , 21 , 3 ] printNGE(arr) # This code is contributed by Sunny Karira |
C#
using System; // c# program to print next // greater element using stack public class NGE { public class stack { public int top; public int [] items = new int [100]; // Stack functions to be used by printNGE public virtual void push( int x) { if (top == 99) { Console.WriteLine( "Stack full" ); } else { items[++top] = x; } } public virtual int pop() { if (top == -1) { Console.WriteLine( "Underflow error" ); return -1; } else { int element = items[top]; top--; return element; } } public virtual bool Empty { get { return (top == -1) ? true : false ; } } } /* prints element and NGE pair for all elements of arr[] of size n */ public static void printNGE( int [] arr, int n) { int i = 0; stack s = new stack(); s.top = -1; int element, next; /* push the first element to stack */ s.push(arr[0]); // iterate for rest of the elements for (i = 1; i < n; i++) { next = arr[i]; if (s.Empty == false ) { // if stack is not empty, then // pop an element from stack element = s.pop(); /* If the popped element is smaller than next, then a) print the pair b) keep popping while elements are smaller and stack is not empty */ while (element < next) { Console.WriteLine(element + " --> " + next); if (s.Empty == true ) { break ; } element = s.pop(); } /* If element is greater than next, then push the element back */ if (element > next) { s.push(element); } } /* push next to stack so that we can find next greater for it */ s.push(next); } /* After iterating over the loop, the remaining elements in stack do not have the next greater element, so print -1 for them */ while (s.Empty == false ) { element = s.pop(); next = -1; Console.WriteLine(element + " -- " + next); } } // Driver Code public static void Main( string [] args) { int [] arr = new int [] { 11, 13, 21, 3 }; int n = arr.Length; printNGE(arr, n); } } // This code is contributed by Shrikant13 |
Javascript
<script> // A Stack based Javascript program to find next // greater element for all array elements. /* prints element and NGE pair for all elements of arr[] of size n */ function printNGE(arr, n) { var s = []; /* push the first element to stack */ s.push(arr[0]); // iterate for rest of the elements for ( var i = 1; i < n; i++) { if (s.length == 0) { s.push(arr[i]); continue ; } /* if stack is not empty, then pop an element from stack. If the popped element is smaller than next, then a) print the pair b) keep popping while elements are smaller and stack is not empty */ while (s.length ==0 == false && s[s.length-1] < arr[i]) { document.write( s[s.length-1] + " --> " + arr[i]+ "<br>" ); s.pop(); } /* push next to stack so that we can find next greater for it */ s.push(arr[i]); } /* After iterating over the loop, the remaining elements in stack do not have the next greater element, so print -1 for them */ while (s.length !=0) { document.write( s[s.length-1] + " --> " + -1+ "<br>" ); s.pop(); } } /* Driver code */ var arr = [11, 13, 21, 3]; var n = arr.length; printNGE(arr, n); </script> |
输出
11 --> 1313 --> 213 --> -121 --> -1
时间复杂性： O（N） 辅助空间： O（N）
最坏的情况发生在所有元素按降序排序时。如果元素按降序排序，则每个元素最多处理4次。
- 最初被推到堆栈中。
- 在处理下一个元素时从堆栈中弹出。
- 因为下一个元素更小，所以被推回堆栈。
- 在算法的第3步从堆栈中弹出。
如何以与输入相同的顺序获取元素？
上述方法可能不会以与输入相同的顺序生成输出元素。为了达到相同的顺序，我们可以按相反的顺序遍历相同的路径
以下是上述方法的实施情况：
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 res pair for all elements of arr[] of size n */ void printNGE( int arr[], int n) { stack< int > s; int res[n]; for ( int i = n - 1; i >= 0; i--) { /* if stack is not empty, then pop an element from stack. If the popped element is smaller than next, then a) print the pair b) keep popping while elements are smaller and stack is not empty */ if (!s.empty()) { while (!s.empty() && s.top() <= arr[i]) { s.pop(); } } res[i] = s.empty() ? -1 : s.top(); s.push(arr[i]); } for ( int i = 0; i < n; i++) cout << arr[i] << " --> " << res[i] << endl; } // Driver Code int main() { int arr[] = { 11, 13, 21, 3 }; int n = sizeof (arr) / sizeof (arr[0]); // Function call 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.Stack; class NextGreaterElement { static int arr[] = { 11 , 13 , 21 , 3 }; /* prints element and NGE pair for all elements of arr[] of size n */ public static void printNGE() { Stack<Integer> s = new Stack<>(); int nge[] = new int [arr.length]; // iterate for rest of the elements for ( int i = arr.length - 1 ; i >= 0 ; i--) { /* if stack is not empty, then pop an element from stack. If the popped element is smaller than next, then a) print the pair b) keep popping while elements are smaller and stack is not empty */ if (!s.empty()) { while (!s.empty() && s.peek() <= arr[i]) { s.pop(); } } nge[i] = s.empty() ? - 1 : s.peek(); s.push(arr[i]); } for ( int i = 0 ; i < arr.length; i++) System.out.println(arr[i] + " --> " + nge[i]); } /* Driver Code */ public static void main(String[] args) { // NextGreaterElement nge = new // NextGreaterElement(); printNGE(); } } |
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 { private int [] arr = new int [] { 11, 13, 21, 3 }; /* prints element and NGE pair for all elements of arr[] of size n */ private void printNGE() { Stack< int > s = new Stack< int >(); int [] nge = new int [arr.Length]; // iterate for rest of the elements for ( int i = arr.Length - 1; i >= 0; i--) { /* if stack is not empty, then pop an element from stack. If the popped element is smaller than next, then a) print the pair b) keep popping while elements are smaller and stack is not empty */ if (s.Count > 0) { while (s.Count > 0 && s.Peek() <= arr[i]) { s.Pop(); } } nge[i] = s.Count == 0 ? -1 : s.Peek(); s.Push(arr[i]); } for ( int i = 0; i < arr.Length; i++) { Console.WriteLine(arr[i] + " --> " + nge[i]); } } // Driver Code public static void Main( string [] args) { GFG nge = new GFG(); nge.printNGE(); } } |
Javascript
<script> // Javascript program for the above approach /* prints element and NGE pair for all elements of arr[] of size n */ function printNGE(arr, n) { var s = []; let res = new Array(n); // iterate for rest of the elements for (let i = n - 1; i >= 0; i--) { /* if stack is not empty, then pop an element from stack. If the popped element is smaller than next, then a) print the pair b) keep popping while elements are smaller and stack is not empty */ if (s.length != 0) { while (s.length != 0 && s[s.length-1] <= arr[i]) { s.pop(); } } res[i] = s.length == 0 ? -1 : s[s.length-1]; s.push(arr[i]); } for (let i = 0; i < arr.length; i++) document.write(arr[i] + " --> " + res[i] + "<br/>" ); } // Driver Code let arr = [ 11, 13, 21, 3 ]; let n = arr.length; // Function call prletNGE(arr, n); // This code is contributed by splevel62. </script> |
输出
11 ---> 1313 ---> 2121 ---> -13 ---> -1
时间复杂性： O（N） 辅助空间： O（N）
方法3：
1.这与上述方法相同，但元素只会被推入堆栈并弹出一次。阵列已更改到位。数组元素被推入堆栈，直到它在数组的右边找到一个最大的元素。换句话说，当当前数组元素中的堆栈顶部值较小时，元素会从堆栈中弹出。
2.一旦数组中的所有元素都被处理，但堆栈不是空的。堆栈中被忽略的元素不会遇到任何最大的元素。因此，从堆栈中弹出元素，并将其索引值更改为数组中的-1。
Python3
# Python3 code class Solution: def nextLargerElement( self ,arr,n): #code here s = [] for i in range ( len (arr)): while s and s[ - 1 ].get( "value" ) < arr[i]: d = s.pop() arr[d.get( "ind" )] = arr[i] s.append({ "value" : arr[i], "ind" : i}) while s: d = s.pop() arr[d.get( "ind" )] = - 1 return arr if __name__ = = "__main__" : print (Solution().nextLargerElement([ 6 , 8 , 0 , 1 , 3 ], 5 )) |
输出
[8, -1, 1, 3, -1]
时间复杂性： O（N） 辅助空间： O（N）
请看一看 针对相同顺序打印的优化解决方案。
如果您发现上述代码/算法不正确，请写下评论，或者寻找其他方法来解决相同的问题。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
