Leetcode #496 Next Greater Eleme

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

直接看代码，维护一个map和一个stack，map的作用是保存每个值的next greater element。
具体过程为，遍历数组，若新来的元素，比stack中的元素小，则直接插入，若新来的元素，比stack顶部的元素大，则该元素即为栈顶元素的next greater element，将栈顶元素pop出来，并保存在map中，并循环该操作，直至栈内元素比新元素都大，再插入新元素。
遍历数组完成后，即得到所有元素的next greater element。
接下来只需要查找新数组的元素了。

类似的题目还有leetcode #503

public class Solution {
    public int[] nextGreaterElements(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        int len = nums.length;
        Stack<Integer> stack = new Stack<>();
        int[] res = new int[len];
        Arrays.fill(res, -1);
        for(int i=0;i<len*2;i++){
            while(!stack.isEmpty()&&nums[stack.peek()]<nums[i%len])
                res[stack.pop()]=nums[i%len];
            if(i<len) stack.push(i);
        }
        return res;
    }
}

此时之前题目中的两个数组变为一个，即假设该数组为头尾相连。
这时候的改法就是遍历数组两遍，并只在第一遍的时候插入栈。