Simple O(m + n) java solution using stack


  • 8
    Z
    public class Solution {
        public int[] nextGreaterElement(int[] findNums, int[] nums) {
            int[] ret = new int[findNums.length];
            ArrayDeque<Integer> stack = new ArrayDeque<>();
            HashMap<Integer, Integer> map = new HashMap<>();
            for(int i = nums.length - 1; i >= 0; i--) {
                while(!stack.isEmpty() && stack.peek() <= nums[i]) {
                    stack.pop();
                }
                if(stack.isEmpty()) map.put(nums[i], -1);
                else map.put(nums[i], stack.peek());
                stack.push(nums[i]);
            }
            for(int i = 0; i < findNums.length; i++) {
                ret[i] = map.get(findNums[i]);
            }
            return ret;
        }
    }
    

  • 0
    H

    Nice try.
    Seems like the way of KMP.


  • 0
    L

    said in Simple O(m + n) java solution using stack:

    you idea is very beautiful.


Log in to reply
 

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