本文共 2789 字,大约阅读时间需要 9 分钟。
Given a circular array (the next element of the last element is the first element of the array), print the Next Greater Number for every element. The Next Greater Number of a number x is the first greater number to its traversing-order next in the array, which means you could search circularly to find its next greater number. If it doesn’t exist, output -1 for this number.
Example 1:
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.Note: The length of given array won’t exceed 10000.
正向走一遍,再反向走一遍把第一遍没找到的与前面比较
我觉得这道题的test cases真的傻逼透了。找不到返回-1,为什么要有[1,8,-1,-100,-1,222,1111111,-111111]
这样的test case???????真的写的火大 class Solution { public int[] nextGreaterElements(int[] nums) { if(nums == null || nums.length <= 0) { return new int[0]; } if(nums.length == 1) { int[] res = { -1}; return res; } int[] res = new int[nums.length]; Arrays.fill(res, -1); int idxRes = 0; while(idxRes < nums.length - 1) { int idxNums = idxRes + 1; while(idxNums < nums.length) { if(nums[idxNums] > nums[idxRes]) { res[idxRes] = nums[idxNums]; break; } idxNums++; } idxRes++; } idxRes = 1; while(idxRes < nums.length) { int idxNums = 0; while(res[idxRes] != -1) { idxRes++; if(idxRes >= nums.length) { break; } } while(idxNums <= idxRes) { if(nums[idxNums] > nums[idxRes]) { res[idxRes] = nums[idxNums]; break; } else { idxNums++; } } idxRes++; } return res; }}
Leetcode solution: Stack
很聪明的方法,用一个stack来模拟循环的过程。感觉循环类的题都可以用stack来模拟class Solution { public int[] nextGreaterElements(int[] nums) { Stackstack = new Stack<>(); int[] res = new int[nums.length]; for(int i = nums.length - 1; i >= 0; i--) { stack.push(nums[i]); } for(int i = nums.length - 1; i >= 0; i--) { while(!stack.isEmpty() && stack.peek() <= nums[i]) { stack.pop(); } if(stack.isEmpty()) { res[i] = -1; } else { res[i] = stack.peek(); } //把自己push进去,便于前一个元素比较 stack.push(nums[i]); } return res; }}
转载地址:http://pyqvb.baihongyu.com/