-
SLPH栈（时间复杂度 O（n））：class Solution(object): def nextGreaterElements(self, nums): """ :type nums: List[int] :rtype: List[int] """ stack = [] size = len(nums) ans = [-1] * size for x in range(size * 2): i = x % size while stack and nums[stack[-1]] < nums[i]: ans[stack.pop()] = nums[i] stack.append(i) return ans -
SLPH朴素解法（时间复杂度 O（n^2））：
public class Solution { public int[] nextGreaterElements(int[] nums) { int size = nums.length; int[] ans = new int[size]; Arrays.fill(ans, -1); for (int i = 0; i < size; i++) { for (int j = i + 1; j % size != i; j++) { if (nums[j % size] > nums[i]) { ans[i] = nums[j % size]; break; } } } return ans; } } -
原题： https://leetcode.com/problems/next-greater-element-ii/description/
题意： 给定一个循环数组（末尾元素的下一个元素为起始元素），输出每一个元素的下一个更大的数字（Next Greater Number）。Next Greater Number是指位于某元素右侧，大于该元素，且距离最近的元素。如果不存在这样的元素，则输出-1。
约定：（1）给定数组长度不超过10000。
例子：
题意： 给定一个循环数组（末尾元素的下一个元素为起始元素），输出每一个元素的下一个更大的数字（Next Greater Number）。Next Greater Number是指位于某元素右侧，大于该元素，且距离最近的元素。如果不存在这样的元素，则输出-1。
约定：（1）给定数组长度不超过10000。
例子：
Input: [1,2,1] Output: [2,-1,2] Explanation: The first 1's next greater number is 2; The number 2 can't find next greater number; The second 1's next greater number needs to search circularly, which is also 2.
标签： greater、number、元素、ii、element、面试
猜你感兴趣的圈子：
