LeetCode下一个更大元素 II

• 问题分析
• 算法复杂度

问题分析

题目给定一个循环数组，输出每个元素的下一个更大元素。
数字 x 的下一个更大的元素是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1。

注意: 输入数组的长度不会超过 10000。

public class Main {public int[] nextGreaterElements(int[] nums) {Stack<Integer> stack = new Stack<Integer>();Map<Integer, Integer> map = new HashMap<>();for (int i = 0; i < 2 * nums.length; i++) {while (!stack.isEmpty() && nums[stack.peek()] < nums[i % nums.length]) {if (map.containsKey(stack.peek())) {stack.pop();} else {map.put(stack.peek(), nums[i % nums.length]);}}stack.push(i % nums.length);}while (!stack.isEmpty()) {if (map.containsKey(stack.peek()))stack.pop();elsemap.put(stack.pop(), -1);}for (int i = 0; i < nums.length; i++) {nums[i] = map.get(i);}return nums;}
}

算法复杂度

时间复杂度：O(n)
空间复杂度：O(n)

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！