【LeetCode力扣】单调栈解决Next Greater Number(下一个更大值)问题

简介: 【LeetCode力扣】单调栈解决Next Greater Number(下一个更大值)问题

1、题目介绍



示例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] <= 10^4
  • nums1和nums2中所有整数 互不相同
  • nums1 中的所有整数同样出现在 nums2 中

2、解题思路

       该题如果使用暴力破解法,其代码实现过程是很容易想到的,只需要找到nums1此时的元素在nums2中的位置,并向右查询是否存在更大的值,有则返回该值,无则返回-1即可。结合思想不难想到时间复杂度为O(m*n),m和n分别为两个数组各自的长度。虽然该题直接使用暴力破解法可以直接通过,但是只是出题人没有为难大家,如果该题的数据非常庞大,此时直接使用暴力破解法必然会导致超时。而本文将讲解单调队列的算法模版解决这类问题,它能够很好的将时间复杂度控制在O(m+n)。


下面将使用两种方法来解题,一种是暴力破解法,一种是Next Greater Number问题解法。


2.1、暴力破解法

从头开始遍历nums1,每次遍历从nums2中找到对应元素,然后从该元素的下一个元素开始依次比较,找出大于该值的第一个元素即可。


【代码实现】


class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        int m = nums1.length, n = nums2.length;
        int[] res = new int[m];
        for (int i = 0; i < m; ++i) {
            int j = 0;
            while (j < n && nums2[j] != nums1[i]) {  //在nums2中找到该值
                ++j;
            }
            int k = j + 1;
            while (k < n && nums2[k] < nums2[j]) {   //从该值的下一个元素开始向右查找
                ++k;
            }
            res[i] = k < n ? nums2[k] : -1;    //超出nums2数组长度则表示不存在比该值大的数,返回-1
        }
        return res;
    }
}

时间复杂度:O(m*n),m和n分别为两数组的长度。


空间复杂度:O(1)。


2.2、经典Next Greater Number问题解法

首先需要补充一些知识点,下面用一个比较抽象的例子讲解:


把数组的元素想象成并列站立的人,元素大小想象成人的身高。视线从左往右,这些人面对你站成一列。如何求第一个元素【2】的下一个更大值呢?,其实很简单,只要没被该元素【2】挡住的第一个元素,就是【2】的下一个更大值,如下图所示,第一个【2】没有挡住的第一个元素就是【4】,此时【4】就是【2】的下一个更大值。



当理解了这个前提后,我们从后往前遍历该数组:


【3】,【3】背后看不到任何元素,即没有比它更大的右元素,因此next greater为-1;


【4】,【4】背后依然看不到任何元素(3被挡住了),此时next greater为-1;


【2】,【2】背后看到的第一个元素是4,因此next greater为4;(绿色2)


【1】,【1】背后看到的第一个元素是2,因此next greater为2;


【2】,【2】背后看到的第一个元素是4,因此next greater为4;(蓝色2)


在代码中为了记录某个值背后没被挡住的第一个元素,这里使用栈stack来记录,入栈出栈规则:当前值比栈中元素大时(证明被挡住了),将该值出栈,直至栈空或当前值小于栈顶元素,此时栈顶元素即为next greater;随后将当前值入栈。


因此我们需要做的就是从后往前遍历nums2数组,并计算出nums2对于的next greater,同时使用Map将【nums2的该值】以及【该值的next greater】记录下来,最后遍历nums1数组,从Map中取出对应值的next greater存入返回数组ret中即可。下面是代码实现部分。


【代码实现】


class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        Stack<Integer> stack = new Stack<>();
        Map<Integer,Integer> map = new HashMap<>();
        for(int i = nums2.length - 1; i >= 0; i--) {   //从后往前
            int num = nums2[i];
            while(!stack.isEmpty() && stack.peek() <= num) {   //栈内元素小于等于当前值时,出栈
                stack.pop();       //让栈始终保持只有【大于】当前值的元素
            }
            map.put(num,stack.isEmpty() ? -1 : stack.peek());   //map记录该值的下一个最大值,没有则-1
            stack.push(num);
        }
        int[] ret = new int[nums1.length];
        for(int i = 0; i < nums1.length; i++) {    //将map中的对应值取出存入返回数组
            ret[i] = map.get(nums1[i]);
        }
        return ret;
    }
}


时间复杂度:O(m+n),m和n分别为两数组的长度。


空间复杂度:O(n),用于存储哈希表。


目录
相关文章
|
4月前
|
Go
【LeetCode 热题100】DP 实战进阶:最长递增子序列、乘积最大子数组、分割等和子集(力扣300 / 152/ 416 )(Go语言版)
本文深入解析三道经典的动态规划问题:**最长递增子序列(LIS)**、**乘积最大子数组** 和 **分割等和子集**。 - **300. LIS** 通过 `dp[i]` 表示以第 `i` 个元素结尾的最长递增子序列长度,支持 O(n²) 动态规划与 O(n log n) 的二分优化。 - **152. 乘积最大子数组** 利用正负数特性,同时维护最大值与最小值的状态转移方程。 - **416. 分割等和子集** 转化为 0-1 背包问题,通过布尔型 DP 实现子集和判断。 总结对比了三题的状态定义与解法技巧,并延伸至相关变种问题,助你掌握动态规划的核心思想与灵活应用!
141 1
|
4月前
|
分布式计算 算法 Go
【LeetCode 热题100】BFS/DFS 实战:岛屿数量 & 腐烂的橘子(力扣200 / 994 )(Go语言版)
本文讲解了两道经典的图论问题:**岛屿数量(LeetCode 200)** 和 **腐烂的橘子(LeetCode 994)**,分别通过 DFS/BFS 实现。在“岛屿数量”中,利用深度或广度优先搜索遍历二维网格,标记连通陆地并计数;“腐烂的橘子”则采用多源 BFS,模拟腐烂传播过程,计算最短时间。两者均需掌握访问标记技巧,是学习网格搜索算法的绝佳实践。
148 1
|
5月前
|
Go 开发者 索引
【LeetCode 热题100】路径与祖先:二叉树中的深度追踪技巧(力扣33 / 81/ 153/154)(Go语言版)
本文深入探讨了LeetCode中四道关于「搜索旋转排序数组」的经典题目,涵盖了无重复和有重复元素的情况。通过二分查找的变形应用,文章详细解析了每道题的解题思路和Go语言实现代码。关键点包括判断有序区间、处理重复元素以及如何缩小搜索范围。文章还总结了各题的异同,并推荐了类似题目,帮助读者全面掌握二分查找在旋转数组中的应用。无论是初学者还是有经验的开发者,都能从中获得实用的解题技巧和代码实现方法。
258 14
|
4月前
|
Go
【LeetCode 热题100】BFS/DFS 实战:岛屿数量 & 腐烂的橘子(力扣200 / 994 )(Go语言版)
本篇博客详细解析了三道经典的动态规划问题:198. 打家劫舍(线性状态转移)、279. 完全平方数与322. 零钱兑换(完全背包问题)。通过 Go 语言实现,帮助读者掌握动态规划的核心思想及其实战技巧。从状态定义到转移方程,逐步剖析每道题的解法,并总结其异同点,助力解决更复杂的 DP 问题。适合初学者深入理解动态规划的应用场景和优化方法。
91 0
|
4月前
|
算法 Go 索引
【LeetCode 热题100】回溯:括号生成 & 组合总和(力扣22 / 39 )(Go语言版)
本文深入解析了LeetCode上的两道经典回溯算法题:**22. 括号生成**与**39. 组合总和**。括号生成通过维护左右括号数量,确保路径合法并构造有效组合;组合总和则允许元素重复选择,利用剪枝优化搜索空间以找到所有满足目标和的组合。两者均需明确路径、选择列表及结束条件,同时合理运用剪枝策略提升效率。文章附有Go语言实现代码,助你掌握回溯算法的核心思想。
111 0
|
6月前
|
Go
【LeetCode 热题100】路径与祖先:二叉树中的深度追踪技巧(力扣437 / 236 )(Go语言版)
本文深入探讨二叉树中路径与祖先问题,涵盖两道经典题目:LeetCode 437(路径总和 III)和236(最近公共祖先)。对于路径总和 III,文章分析了双递归暴力解法与前缀和优化方法,后者通过哈希表记录路径和,将时间复杂度从O(n²)降至O(n)。在最近公共祖先问题中,采用后序遍历递归查找,利用“自底向上”的思路确定最近公共祖先节点。文中详细解析代码实现与核心要点,帮助读者掌握深度追踪技巧,理解树结构中路径与节点关系的本质。这类问题在面试中高频出现,掌握其解法意义重大。
124 4
|
6月前
|
算法 Go
【LeetCode 热题100】深入理解二叉树结构变化与路径特性(力扣104 / 226 / 114 / 543)(Go语言版)
本博客深入探讨二叉树的深度计算、结构变换与路径分析,涵盖四道经典题目:104(最大深度)、226(翻转二叉树)、114(展开为链表)和543(二叉树直径)。通过递归与遍历策略(前序、后序等),解析每题的核心思路与实现方法。结合代码示例(Go语言),帮助读者掌握二叉树相关算法的精髓。下一讲将聚焦二叉树构造问题,欢迎持续关注!
140 10
|
12月前
|
程序员 C语言
【C语言】LeetCode(力扣)上经典题目
【C语言】LeetCode(力扣)上经典题目
204 1
|
12月前
【LeetCode 24】225.用队列实现栈
【LeetCode 24】225.用队列实现栈
76 0
|
12月前
|
索引
力扣(LeetCode)数据结构练习题(3)------链表
力扣(LeetCode)数据结构练习题(3)------链表
237 0

热门文章

最新文章