博客

leetode每日一题之下一个更大的元素

题目链接

：https://leetcode-cn.com/problems/next-greater-element-i/

题目描述

：

给你两个 没有重复元素 的数组 nums1 和 nums2 ，其中nums1 是 nums2 的子集。

请你找出 nums1 中每个元素在 nums2 中的下一个比其大的值。

nums1 中数字 x 的下一个更大元素是指 x 在 nums2 中对应位置的右边的第一个比 x 大的元素。如果不存在，对应位置输出 -1 。

示例 1:
输入: nums1 = [4,1,2], nums2 = [1,3,4,2].
输出: [-1,3,-1]
解释:
    对于 num1 中的数字 4 ，你无法在第二个数组中找到下一个更大的数字，因此输出 -1 。
    对于 num1 中的数字 1 ，第二个数组中数字1右边的下一个较大数字是 3 。
    对于 num1 中的数字 2 ，第二个数组中没有下一个更大的数字，因此输出 -1 。

示例 2:
输入: nums1 = [2,4], nums2 = [1,2,3,4].
输出: [3,-1]
解释:
    对于 num1 中的数字 2 ，第二个数组中的下一个较大数字是 3 。
    对于 num1 中的数字 4 ，第二个数组中没有下一个更大的数字，因此输出 -1 。

解法1：栈+哈希表

https://leetcode-cn.com/problems/next-greater-element-i/solution/dong-hua-yan-shi-dan-diao-zhan-496xia-yi-ql65/

代码：

    package com.tao.stack;
    import java.util.HashMap;
    import java.util.Map;
    import java.util.Stack;
    /**
     * @Classname NextGreaterElement
     * @Description TODO
     * @Date 2021/7/8 17:54
     * @Author Anonymous
     */
    @SuppressWarnings("all")
    public class NextGreaterElement {
        public static void main(String[] args) {
            int[] nums1 = {4, 1, 2};
            int[] nums2 = {1, 3, 4, 2};
            int[] ints = nextGreaterElement(nums1, nums2);
            for (int anInt : ints) {
                System.out.println(anInt);
            }
        }
    
        //输入: nums1 = [4,1,2], nums2 = [1,3,4,2].
        //输出: [-1,3,-1]
        public static int[] nextGreaterElement(int[] nums1, int[] nums2) {
            int[] array = new int[nums1.length];
            int i = 0;
            Map<Integer, Integer> helper = helper(nums2);
            for (int num : nums1) {
                Integer integer = helper.get(num);
                array[i++] = integer;
            }
            return array;
        }
    
        public static Map<Integer, Integer> helper(int nums[]) {
            //初始化栈和map集合
            Stack<Integer> stack = new Stack<>();
            Map<Integer, Integer> map = new HashMap();
            for (int i = 0; i < nums.length; i++) {
                //栈不为空且当前元素大于栈顶元素，说明当前元素是栈顶元素的下一个更大的元素
                while (!stack.isEmpty() && nums[i] > stack.peek()) {
                    map.put(stack.pop(), nums[i]);
                }
                //将当前考察元素入栈，看是否有其下一个元素
                stack.push(nums[i]);
            }
            //【1，3，4，2】 的 4 2 最后都在栈中
            while (!stack.isEmpty()) {
                map.put(stack.pop(),-1);
            }
    
            //不能这样写，因为栈顶元素在出栈，所以栈的size在改变
    //        for (int i = 0;i < stack.size();i++) {
    //            map.put(stack.pop(),-1);
    //        }
            return map;
        }
    }

一般找下一个更大的元素这种题要用到栈这种数据结构

解法2：暴力法

代码：暴力法自己想的，妈的调试很久才出来，真是菜啊！

    //暴力法
        //输入: nums1 = [4,1,2], nums2 = [1,3,4,2].
        //输出: [-1,3,-1]
        public static int[] nextGreaterElement2(int[] nums1, int[] nums2) {
            int[] array = new int[nums1.length];
            int m = 0;
            for (int i = 0; i < nums1.length; i++) {
                int num = nums1[i];
                int j = 0;
                while (j < nums2.length && num != nums2[j]) {
                    j++;
                }
                //此时nums1[i] == nums2[j]
                j++;
                int k;
                for (k = j; k < nums2.length; k++) {
                    if (nums2[k] > nums1[i]) {
                        array[m++] = nums2[k];
                        break;//找到之后要跳出循环
                    }
                }
                //因为找到之后还要执行这段代码，如果不加if判断是否走完整个nums2的元素，就会接着赋值-1
                if (k == nums2.length) {
                    array[m++] = -1;
                }
            }
            return array;
        }

评论区中看到的用集合的暴力法，感觉挺好的，如下：

    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
            int[] res = new int[nums1.length];
            Arrays.fill(res, -1);
            Map<Integer, Integer> map = new HashMap<>();
            for (int i = 0; i < nums2.length; i++){
                map.put(nums2[i], i);
            }
            for (int i = 0; i < nums1.length ; i++) {
                for (int j = map.get(nums1[i]); j < nums2.length; j++) {
                    if (nums2[j] > nums1[i]) {
                        res[i] = nums2[j];
                        break;
                    }
                }
            }
            return res;
        }
    
    作者：wang-xue-lei-2
    链接：https://leetcode-cn.com/problems/next-greater-element-i/solution/3msde-bao-li-he-5msde-dan-diao-zhan-by-w-g61s/
    来源：力扣（LeetCode）
    著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。