Next Greater Element I
给两个数组A,B, A数组是B数组的子数组, 求一个数组C, 使得C每一个数字在B都大于A. 这个题可以直接扫, 就是n^2的复杂度, 也可以用一个stack倒着装数组的元素, 然后用一个map记录位置, 这样在B里每遇到一个元素, 都在stack里找一下. 注意B里没有一个大于A的(比如, 倒排序), 这时候要用-1取代位置.
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;
}
}