每日一练:LeeCode-496. 下一个更大元素 I(简)【单调栈】

发布时间:2023年12月30日

本文是力扣LeeCode-496. 下一个更大元素 I 学习与理解过程,本文仅做学习之用,对本题感兴趣的小伙伴可以出门左拐LeeCode。

nums1 中数字 x 的 下一个更大元素 是指 x 在 nums2 中对应位置 右侧第一个 比 x 大的元素。
给你两个 没有重复元素 的数组 nums1 和 nums2 ,下标从 0 开始计数,其中nums1 是 nums2 的子集。
对于每个 0 <= i < nums1.length ,找出满足 nums1[i] == nums2[j] 的下标 j ,并且在 nums2 确定 nums2[j] 的 下一个更大元素 。如果不存在下一个更大元素,那么本次查询的答案是 -1 。
返回一个长度为 nums1.length 的数组 ans 作为答案,满足 ans[i] 是如上所述的 下一个更大元素

示例 1:
输入:nums1 = [4,1,2], nums2 = [1,3,4,2].
输出:[-1,3,-1]
解释:nums1 中每个值的下一个更大元素如下所述:
4 ,用加粗斜体标识,nums2 = [1,3,4,2]。不存在下一个更大元素,所以答案是 -1 。
1 ,用加粗斜体标识,nums2 = [1,3,4,2]。下一个更大元素是 3 。
2 ,用加粗斜体标识,nums2 = [1,3,4,2]。不存在下一个更大元素,所以答案是 -1 。

示例 2:
输入:nums1 = [2,4], nums2 = [1,2,3,4].
输出:[3,-1]
解释:nums1 中每个值的下一个更大元素如下所述:
2 ,用加粗斜体标识,nums2 = [1,2,3,4]。下一个更大元素是 3 。
4 ,用加粗斜体标识,nums2 = [1,2,3,4]。不存在下一个更大元素,所以答案是 -1 。

提示:
1 <= nums1.length <= nums2.length <= 1000
0 <= nums1[i], nums2[i] <= 104
nums1和nums2中所有整数 互不相同
nums1 中的所有整数同样出现在 nums2 中

直接暴力法O(n2)

本题直接暴力解决,也简单易懂,但是时间复杂度O(n2)

class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        int[] res = new int[nums1.length];
        int first=0;	//nums2中对应x值的下标
        for(int i=0;i<nums1.length;i++){
            for(int j=0;j<nums2.length;j++){	//从头开始遍历
                if(nums1[i]==nums2[j]){	//直到在nums2中找到x的值,并记录下标
                    first=j;
                }else{
                    continue;	
                }
            }
            for(int m=first;m<nums2.length;m++){
                if(nums1[i]<nums2[m]){	//从对应下标开始,在nums2中找到第一个大于x的数
                    res[i]=nums2[m];
                    break;	//直接结束一趟循环
                }else{
                    res[i]=-1;	//没找到就一直赋值为-1
                    continue;
                }
            }
        }
        return res;
    }
}

单调栈+哈希

单调栈专门解决Next Greater Number

单调栈解决,可以参考labuladong博主的文章,我也是从他的文章那学习理解的。
问题抽象思考
把数组的元素想象成并列站立的人,元素大小想象成人的身高。这些人面对你站成一列,如何求元素「2」的 Next Greater Number 呢?很简单,如果能够看到元素「2」,那么他后面可见的第一个人就是「2」的 Next Greater Number,因为比「2」小的元素身高不够,都被「2」挡住了,第一个
露出来的就是答案。

                            ------->
                            |      ------>
        ------------------->|      |
        |       ------>|    |      |
        |       |      |--->|      |
        2       1      2    4      3
        4       2      4    -1     -1

这个算法的时间复杂度不是那么直观,虽然你看到 for 循环嵌套 while 循环,可能认为这个算法的复杂度也是 O(n^2),但是实际上这个算法的复杂度只有 O(n)

class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        int[] result = new int[nums1.length];
        Map<Integer,Integer> map = nextGreaterHelper(nums2);
        for(int i=0;i<nums1.length;i++){
            result[i] = map.get(nums1[i]);
        }
        return result;
    }

    private Map<Integer,Integer> nextGreaterHelper(int[] nums){
        Map<Integer,Integer> map = new HashMap<>();
        Stack<Integer> stack = new Stack<>();	// 存放高个元素的栈
        for(int i=nums.length-1;i>=0;i--){	// 倒着往栈里放
            while(!stack.isEmpty()&&stack.peek()<nums[i]){
                stack.pop();	// 弹出矮个子,反正都被挡着了
            }
            map.put(nums[i],stack.isEmpty()?-1:stack.peek());//当前元素身后的第一个高个子
            stack.push(nums[i]);	//进入栈中,接受身高评定	
        }
        return map;
    }
}

总体来说,单调栈是解决Next Greater Number的好办法,对这个方法理解之后,大家可以尝试去刷
503.下一个更大元素II
1118.一月有多少天

大家有更好的方法,请不吝赐教。

文章来源:https://blog.csdn.net/kdzandlbj/article/details/135308184
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。