package stack;

import java.util.*;

/**
 * @author dx
 * @version 1.0
 * @date 2022年3月28日 17:09
 * @description: nums1中数字x的下一个更大元素是指z在nums2中对应位置右侧的第一个比x大的元素
 */
public class NextGreaterNum {

 public static void main(String []args){
 int []test1 = {4,1,2};
 int []test2 = {1,3,4,2};
 int []result = new int[3];
 result = nextGreaterElement2(test1,test2);
 for(int num: result){
 System.out.println(num);
 }
 }
 //方法1
 public static int[] nextGreaterElement(int[] nums1, int[] nums2) {

 int len1 = nums1.length;
 int len2 = nums2.length;
 List<Integer> list = new ArrayList<Integer>();
 int []result = new int[len1];

 //将数组2的元素添加到ArrayList中去 共len2个
 for(int i =0;i<len2;i++){
 list.add(nums2[i]);
 }
 for(int i=0;i<len1;i++){ //遍历数组1
 int obj = list.indexOf(nums1[i]);//数组2中出现该元素的索引值
 int tmp = 0;
 while(obj<len2){
 obj++;
 if(obj == len2){
 result[i] = -1;
 break;
 }
 tmp = list.get(obj);
 if(tmp>nums1[i]){
 result[i] = tmp;
 break;
 }
 }
 }
 return result;
 }
 //方法2:通过栈 记录每个元素最右边第一个比自己大的元素,然后通过HashMap记录下来
 public static int[] nextGreaterElement2(int[] nums1, int[] nums2){
 // ArrayDeque 基于数组实现双端队列,
 // 而 LinkedList 基于双向链表实现双端队列,数组采用连续的内存地址空间,通过下标索引访问,
 // 链表是非连续的内存地址空间,通过指针访问,所以在寻址方面数组的效率高于链表。
 Deque<Integer> stack = new ArrayDeque<Integer>();
 Map<Integer,Integer> map = new HashMap<Integer,Integer>();

 for(int i=nums2.length-1;i>=0;--i){
 while (!stack.isEmpty() && nums2[i]>=stack.peek()){
 stack.pop();
 }
 map.put(nums2[i],stack.isEmpty()? -1:stack.peek()); //考虑到最后一个元素一定在右边没有一个最大值
 stack.push(nums2[i]); //把当前的值存到栈顶,保证下一个元素找最近比自己大的元素
 }
 int [] res = new int[nums1.length];
 for(int i = 0;i<nums1.length;i++){
 res[i] = map.get(nums1[i]);
 }
 return res;
 }
}