力扣AC：下一个更大的元素 - 单调栈 哈希表

题目链接

下一个更大的元素

题目描述

实现代码

思路：首先需要理清题意，是找到nums1数组中的每个元素在nums2中对应的位置开始往后的第一个大于该值的数值；

暴力破解法两层循环是最容易想到的思路，就不多阐述；

这里采用单调栈 + 哈希表的形式进行优化实现；

1. 单调栈：用于将nums2数组的元素进行遍历，从而找到当前位置往后的第一个大于该值的元素值；
2. 哈希表：用于将单调栈获取到的结果进行保存；

首先，将数组nums2中的每个元素从后往前进行遍历，按照栈顶元素最大的原则对其进行遍历压入栈中，同时在哈希表中保存当前元素对应的下一个大的值为栈顶元素；遍历压入期间如果遇到元素大于当前栈顶元素，则将当前栈顶元素剔除，直到满足单调栈的条件或者栈为空

实现代码如下：

class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        int len1 = nums1.length;
        int len2 = nums2.length;
        if(len2 == 1) {
            return new int[]{-1};
        }
        Map<Integer, Integer> map = new HashMap<>(len2 << 1);
        Stack<Integer> stack = new Stack<>();
        stack.push(nums2[len2-1]);
        map.put(nums2[len2-1], -1);
        for(int i=len2-2; i>=0; i--) {
            int val = nums2[i];
            while (!stack.isEmpty()) {
                int topVal = stack.peek();
                if(topVal > val) {
                    stack.push(val);
                    map.put(val, topVal);
                    break;
                }
                stack.pop();
            }
            if(stack.isEmpty()) {
                stack.push(val);
                map.put(val, -1);
            }
        }
        int[] results = new int[len1];
        for(int i=0; i<len1; i++) {
            results[i] = map.get(nums1[i]);
        }
        return results;
    }
}