题目链接
题目描述
实现代码
思路:首先需要理清题意,是找到nums1数组中的每个元素在nums2中对应的位置开始往后的第一个大于该值的数值;
暴力破解法两层循环是最容易想到的思路,就不多阐述;
这里采用单调栈 + 哈希表的形式进行优化实现;
- 单调栈:用于将nums2数组的元素进行遍历,从而找到当前位置往后的第一个大于该值的元素值;
- 哈希表:用于将单调栈获取到的结果进行保存;
首先,将数组nums2中的每个元素从后往前进行遍历,按照栈顶元素最大的原则对其进行遍历压入栈中,同时在哈希表中保存当前元素对应的下一个大的值为栈顶元素;遍历压入期间如果遇到元素大于当前栈顶元素,则将当前栈顶元素剔除,直到满足单调栈的条件或者栈为空
实现代码如下:
class Solution {
public int[] nextGreaterElement(int[] nums1, int[] nums2) {
int len1 = nums1.length;
int len2 = nums2.length;
if(len2 == 1) {
return new int[]{-1};
}
Map<Integer, Integer> map = new HashMap<>(len2 << 1);
Stack<Integer> stack = new Stack<>();
stack.push(nums2[len2-1]);
map.put(nums2[len2-1], -1);
for(int i=len2-2; i>=0; i--) {
int val = nums2[i];
while (!stack.isEmpty()) {
int topVal = stack.peek();
if(topVal > val) {
stack.push(val);
map.put(val, topVal);
break;
}
stack.pop();
}
if(stack.isEmpty()) {
stack.push(val);
map.put(val, -1);
}
}
int[] results = new int[len1];
for(int i=0; i<len1; i++) {
results[i] = map.get(nums1[i]);
}
return results;
}
}