Next Greater Element I
给两个数组A,B, A数组是B数组的子数组, 求一个数组C, 使得C每一个数字在B都大于A. 这个题可以直接扫, 就是n^2的复杂度, 也可以用一个stack倒着装数组的元素, 然后用一个map记录位置, 这样在B里每遇到一个元素, 都在stack里找一下. 注意B里没有一个大于A的(比如, 倒排序), 这时候要用-1取代位置.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
public class Solution { public int[] nextGreaterElement(int[] findNums, int[] nums) { Stack < Integer > stack = new Stack < > (); HashMap < Integer, Integer > map = new HashMap < > (); int[] res = new int[findNums.length]; for (int i = 0; i < nums.length; i++) { while (!stack.empty() && nums[i] > stack.peek()) map.put(stack.pop(), nums[i]); stack.push(nums[i]); } while (!stack.empty()) map.put(stack.pop(), -1); for (int i = 0; i < findNums.length; i++) { res[i] = map.get(findNums[i]); } return res; } } |