public class Solution {
public int[] nextGreaterElement(int[] findNums, int[] nums) {
Map<Integer, Integer> map = new HashMap<>();
Stack<Integer> stack = new Stack<>();
int[] res = new int[findNums.length];
for(int num:nums){
while(!stack.isEmpty()&&stack.peek()<num)
map.put(stack.pop(), num);
stack.push(num);
}
for(int i=0;i<findNums.length;i++){
res[i] = map.getOrDefault(findNums[i], -1);
}
return res;
}
}
直接看代码，维护一个map和一个stack，map的作用是保存每个值的next greater element。
具体过程为，遍历数组，若新来的元素，比stack中的元素小，则直接插入，若新来的元素，比stack顶部的元素大，则该元素即为栈顶元素的next greater element，将栈顶元素pop出来，并保存在map中，并循环该操作，直至栈内元素比新元素都大，再插入新元素。
遍历数组完成后，即得到所有元素的next greater element。
接下来只需要查找新数组的元素了。
类似的题目还有leetcode #503
public class Solution {
public int[] nextGreaterElements(int[] nums) {
Map<Integer, Integer> map = new HashMap<>();
int len = nums.length;
Stack<Integer> stack = new Stack<>();
int[] res = new int[len];
Arrays.fill(res, -1);
for(int i=0;i<len*2;i++){
while(!stack.isEmpty()&&nums[stack.peek()]<nums[i%len])
res[stack.pop()]=nums[i%len];
if(i<len) stack.push(i);
}
return res;
}
}
此时之前题目中的两个数组变为一个，即假设该数组为头尾相连。
这时候的改法就是遍历数组两遍，并只在第一遍的时候插入栈。
