（題目來(lái)源:力扣LeetCode)
題目：給你兩個(gè) 沒(méi)有重復(fù)元素 的數(shù)組?nums1 和?nums2?，其中nums1?是?nums2?的子集。
請(qǐng)你找出 nums1?中每個(gè)元素在?nums2?中的下一個(gè)比其大的值。
nums1?中數(shù)字?x?的下一個(gè)更大元素是指?x?在?nums2?中對(duì)應(yīng)位置的右邊的第一個(gè)比?x?大的元素。如果不存在，對(duì)應(yīng)位置輸出 -1 。
示例 1
輸入: nums1 = [4,1,2], nums2 = [1,3,4,2].
輸出: [-1,3,-1]
解釋:
? ? 對(duì)于 num1 中的數(shù)字 4 ，你無(wú)法在第二個(gè)數(shù)組中找到下一個(gè)更大的數(shù)字，因此輸出 -1 。
? ? 對(duì)于 num1 中的數(shù)字 1 ，第二個(gè)數(shù)組中數(shù)字1右邊的下一個(gè)較大數(shù)字是 3 。
? ? 對(duì)于 num1 中的數(shù)字 2 ，第二個(gè)數(shù)組中沒(méi)有下一個(gè)更大的數(shù)字，因此輸出 -1 。
方法一：暴力解法
題解：
1、先找出在nums2中與num1s中先對(duì)應(yīng)的元素的索引
2、從該元素的索引往后遍歷，找到第一個(gè)大于該元素的數(shù)，如果沒(méi)有找到就返回-1
classSolution{
? ? public int[] nextGreaterElement(int[] nums1, int[] nums2) {
? ? ? ? int[] array = new int[nums1.length];
? ? ? ? for(int i=0;i<nums1.length;i++){
? ? ? ? ? ? int j=0;
? ? ? ? ? ? while(nums1[i]!=nums2[j])
? ? ? ? ? ? j++;? ? ? ? ? ?
? ? ? ? ? ? for(int k=j+1;k<=nums2.length;k++){
? ? ? ? ? ? ? if(k>=nums2.length){
? ? ? ? ? ? ? ? array[i]=-1;
? ? ? ? ? ? ? ? break;
? ? ? ? ? ? ? }
? ? ? ? ? ? ? if(nums2[k]>nums2[j]){
? ? ? ? ? ? ? ? array[i]=nums2[k];
? ? ? ? ? ? ? ? break;
? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? return array;
? ? }
}
時(shí)間復(fù)雜度：O（MN），M、N分別是兩個(gè)數(shù)組的長(zhǎng)度
方法二：?jiǎn)握{(diào)棧+哈希表
題解：
1、先遍歷nums2，并且尋找nums2中每個(gè)元素后面第一個(gè)比本元素大的元素。
2、在遍歷的過(guò)程中，將每一個(gè)元素入棧，如果遇到了后一個(gè)比棧頂元素大的值，就將棧頂元素出棧、比棧頂元素大的值入棧，并且將棧頂元素作為鍵（Key），比棧頂元素大的元素作為值（Value）存入哈希表中。如果后一個(gè)元素比棧頂元素小，那么棧頂元素不動(dòng)，后一個(gè)元素壓棧，直到遇到了一個(gè)元素比當(dāng)前的棧頂元素大，那么棧頂元素出棧、比棧頂元素大的值入棧，并且將棧頂元素作為鍵（Key），比棧頂元素大的元素作為值（Value）存入哈希表中。
3、遍歷nums1，并且訪問(wèn)哈希表，得到每一個(gè)與nums2相應(yīng)的元素的哈希值（其實(shí)就是后一個(gè)最大元素），如果有元素找不到哈希值，就代表它沒(méi)有下一個(gè)更大元素，返回-1
public int[] nextGreaterElement(int[] nums1, int[] nums2) {
? ? ? ? int len1 = nums1.length;
? ? ? ? int len2 = nums2.length;
? ? ? ? Deque<Integer> stack = new ArrayDeque<>();
? ? ? ? Map<Integer,Integer> map = new HashMap<>();
? ? ? ? //先判斷num2,把對(duì)應(yīng)關(guān)系存入哈希表? ? ? ? for(int i=0;i<len2;i++){
? ? ? ? ? ? while(!stack.isEmpty() && stack.peekLast()<nums2[i]){
? ? ? ? ? ? ? ? map.put(stack.removeLast(),nums2[i]);
? ? ? ? ? ? }
? ? ? ? ? ? stack.addLast(nums2[i]);
? ? ? ? }
? ? ? ? int [] res = new int [len1];
? ? ? ? //在遍歷num1? ? ? ? for(int i =0;i<len1;i++){
? ? ? ? ? ? res[i]=map.getOrDefault(nums1[i],-1);
? ? ? ? }
? ? ? ? return res;
? ? }
