电商网站建设维护费会计分录,盘龙区网络推广,网站设计有限公司是干嘛的,站长工具seo综合查询官网本文是力扣LeeCode-503. 下一个更大元素 II 学习与理解过程#xff0c;本文仅做学习之用#xff0c;对本题感兴趣的小伙伴可以出门左拐LeeCode。 给定一个循环数组 nums #xff08; nums[nums.length - 1] 的下一个元素是 nums[0] #xff09;#xff0c;返回 nums 中每个…本文是力扣LeeCode-503. 下一个更大元素 II 学习与理解过程本文仅做学习之用对本题感兴趣的小伙伴可以出门左拐LeeCode。 给定一个循环数组 nums nums[nums.length - 1] 的下一个元素是 nums[0] 返回 nums 中每个元素的 下一个更大元素 。 数字 x 的 下一个更大的元素 是按数组遍历顺序这个数字之后的第一个比它更大的数这意味着你应该循环地搜索它的下一个更大的数。如果不存在则输出 -1 。 示例 1: 输入: nums [1,2,1] 输出: [2,-1,2] 解释: 第一个 1 的下一个更大的数是 2 数字 2 找不到下一个更大的数 第二个 1 的下一个最大的数需要循环搜索结果也是 2。 示例 2: 输入: nums [1,2,3,4,3] 输出: [2,3,4,-1,4] 单调栈法单调栈法是我们刷算法必备的黄金公式 对单调栈的理解我参考 负雪明烛博主的讲解 在实现上我们可以使用**「单调栈」**来实现单调栈是说 栈里面的元素从栈底到栈顶是 单调递增或者单调递减的类似于汉诺塔。本题应该用个「单调递减栈」来实现。 建立「单调递减栈」并对原数组遍历一次 如果栈为空则把当前元素放入栈内 如果栈不为空则需要判断当前元素和栈顶元素的大小 如果当前元素比栈顶元素大说明当前元素是前面一些元素的「下一个更大元素」则逐个弹出栈顶元素直到当前元素比栈顶元素小为止。 如果当前元素比栈顶元素小说明当前元素的「下一个更大元素」与栈顶元素相同则把当前元素入栈。
模版以 下一个更大元素 I 为例
class Solution {public int[] nextGreaterElement(int[] nums1, int[] nums2) {MapInteger, Integer map new HashMapInteger, Integer();DequeInteger stack new ArrayDequeInteger();for (int i nums2.length - 1; i 0; --i) {int num nums2[i];while (!stack.isEmpty() num stack.peek()) {stack.pop();}map.put(num, stack.isEmpty() ? -1 : stack.peek());stack.push(num);}int[] res new int[nums1.length];for (int i 0; i nums1.length; i) {res[i] map.get(nums1[i]);}return res;}
}思路
考虑到本题的实际情况需要回过头来遍历数组这里牵扯到 循环数组 的概念。 循环数组数组的最后一个元素下一个元素是数组的第一个元素形状类似于「环」。我们只需要使用 取模运算 % 可以把下标i映射到数组 nums长度的 0−N内。
未通过版本
参照下一个更大元素 I 的解决方法并结合循环数据我的代码如下 public int[] nextGreaterElements(int[] nums) {int[] result new int[nums.length];MapInteger,Integer map nextGreaterElementsHelper(nums);for(int i0;inums.length;i){result[i] map.get(nums[i]);}return result;}private MapInteger,Integer nextGreaterElementsHelper(int[] nums){int len nums.length;MapInteger,Integer map new HashMap();StackInteger stack new Stack();for(int j2*len-1;j0;j--){ //逻辑环取模运算while(!stack.isEmpty()stack.peek()nums[j%len]){stack.pop();}map.put(nums[j%len],stack.isEmpty()?-1:stack.peek());stack.push(nums[j%len]);}return map;}提交报错 从1开始就出问题了debug了半天没看出问题。有大佬帮我看出问题吗
代码实现
class Solution {public int[] nextGreaterElements(int[] nums) {int n nums.length;int[] ret new int[n];Arrays.fill(ret, -1);DequeInteger stack new LinkedListInteger();for (int i 0; i n * 2 - 1; i) {while (!stack.isEmpty() nums[stack.peek()] nums[i % n]) {ret[stack.pop()] nums[i % n];}stack.push(i % n);}return ret;}
}大家有更好的方法请不吝赐教。
