Stack, Java O(n) with explanation


  • 1
    A

    Solution is based on using the stack for tracking the greater elements from the array. We know that for each number there may exist only one greater number which stays on the right side from itself.
    We can use Stack. Stack will have numbers in decreasing order. if num[I] is greater than peek element of the stack then num[I] will be answer for peek element. Summarizing, we can remove peek elements until nums[I] will be less than peek element and for all removed numbers the answer will be nums[I].

    public class Solution {
        public int[] nextGreaterElement(int[] findNums, int[] nums) {
            HashMap<Integer, Integer> greater = new HashMap<>();
            Stack<Integer> stack = new Stack<Integer>();
            for (int num: nums) {
                while (!stack.isEmpty() && stack.peek()<num) {
                    int val = stack.pop();
                    greater.put(val, num);
                }
                stack.push(num);
            }
            
            int ans[] = new int[findNums.length];
            for (int i=0; i<findNums.length; i++) {
                Integer val = greater.get(findNums[i]);
                if (val==null) val = -1;
                ans[i] = val;
            }
            return ans;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.