Next Greater Element I

给两个数组A,B, A数组是B数组的子数组, 求一个数组C, 使得C每一个数字在B都大于A. 这个题可以直接扫, 就是n^2的复杂度, 也可以用一个stack倒着装数组的元素, 然后用一个map记录位置, 这样在B里每遇到一个元素, 都在stack里找一下. 注意B里没有一个大于A的(比如, 倒排序), 这时候要用-1取代位置.

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