力扣-496题（Java）-单调栈+哈希

迈不过友情╰ 2023-01-22 12:50 10阅读 0赞

题目链接：[https://leetcode-cn.com/problems/next-greater-element-i/][https_leetcode-cn.com_problems_next-greater-element-i]  
题目如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNDY3Njcw_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNDY3Njcw_size_16_color_FFFFFF_t_70 1]

class Solution {
        
        public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        
    
            //tip:
            //1、单调栈：栈中的元素从栈顶到栈底是单调不降低的
            //2、对nums2先行处理，nums1只适用于key查找对应的value
            //3、确定key-value思路：always往stack中放元素，直到出现比栈顶元素大的值时，出找；并存入hash
            //4、自己没考虑到的注意点：只要栈顶元素能出栈，就一直判断能否继续出栈，直到不能出为止，再将当前值入栈；继续3操作
            //5、当get不到hash中的value时，应该hashmap.getOrDefault(nums1[i],-1); 否则会报错
    
            LinkedList<Integer> stack=new LinkedList<Integer>();
            HashMap<Integer,Integer> hashmap=new HashMap<Integer,Integer>();
    
            for(int i=0;i<nums2.length;i++){
        
                //注意点：while
                while(!stack.isEmpty()&&stack.getLast()<nums2[i]){
        
                    hashmap.put(stack.getLast(),nums2[i]);
                    stack.removeLast();   
                }
                stack.addLast(nums2[i]);
            }
            //System.out.println(hashmap);//用于输出当前的哈希键值对
            for(int i=0;i<nums1.length;i++)
                nums1[i]=hashmap.getOrDefault(nums1[i],-1);
                
            return nums1;
        }
    }

[https_leetcode-cn.com_problems_next-greater-element-i]: https://leetcode-cn.com/problems/next-greater-element-i/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNDY3Njcw_size_16_color_FFFFFF_t_70]: /images/20221020/5a0966700cda48feb64ed386f8efd029.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNDY3Njcw_size_16_color_FFFFFF_t_70 1]: /images/20221020/32c46119b4e24bde84db09e0ed678893.png