题目: 算法思想: 具体流程如下:
创建一个临时栈,一个哈希表,然后遍历 nums2 若当前栈无数据,则当前数字入栈备用。 若当前栈有数据,则用当前数字与栈顶比较: 3.1 当前数字 > 栈顶,代表栈顶对应下一个更大的数字就是当前数字,则将该组数字对应关系,记录到哈希表。 3.2 当前数字 < 栈顶,当前数字压入栈,供后续数字判断使用。 这样,我们就可以看到哈希表中存在部分 nums2数字的对应关系了,而栈中留下的数字,代表无下一个更大的数字,我们全部赋值为 -1 ,然后存入哈希表即可。 遍历 nums1,直接询问哈希表拿对应关系即可。
代码:
class Solution {
public static int[] nextGreaterElement(int[] nums1, int[] nums2) {
Stack<Integer> stack = new Stack<>();
HashMap<Integer, Integer> hash = new HashMap<>();
List<Integer> list = new ArrayList<>();
for (Integer num : nums2) {
while (!stack.isEmpty() && stack.peek() < num) {
Integer pop = stack.pop();
hash.put(pop, num);
}
stack.push(num);
}
while(!stack.isEmpty()) {
Integer pop = stack.pop();
hash.put(pop, -1);
}
for (Integer num : nums1) {
list.add(hash.get(num));
}
int result[] = new int[list.size()];
for (int i = 0; i < list.size(); i++) {
result[i] = list.get(i);
}
return result;
}
}
|