Algorithm to find next greater element in array for current element.
If we do linear search then it would take O(n^2) but here we are going to use stack to implement this algorithm. It will going to take O(n) time.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 |
package com.omt.learn.algo; import java.util.Stack; /** * Created by dhpandya on 3/29/17. */ public class NextGreaterElement { public static void main(String args[]) { int a[] = {98, 23, 54, 12, 20, 7, 27}; int result[] = getNextGreaterElements(a); for (int i : result) { System.out.println(i); } } private static int[] getNextGreaterElements(int a[]) { int nextGreaterElms[] = new int[a.length]; nextGreaterElms[a.length - 1] = -1; Stack<Integer> indexStack = new Stack<>(); Stack<Integer> greaterElmsStack = new Stack<>(); greaterElmsStack.push(a[0]); indexStack.push(0); int index = 1; while (index < a.length) { while (greaterElmsStack.peek() < a[index]) { nextGreaterElms[indexStack.pop()] = a[index]; greaterElmsStack.pop(); } indexStack.push(index); greaterElmsStack.push(a[index]); index++; } while (!indexStack.empty()) { nextGreaterElms[indexStack.pop()] = -1; greaterElmsStack.pop(); } return nextGreaterElms; } } |
Output
-1
54
-1
20
27
27
-1