496. 下一個更大元素 I

解題思路

• 首先計算nums2的每一個元素的下一個比他大的元素，使用單調(diào)棧
• 將上面的結(jié)果和nums2中的每一個元素組成映射map
• 針對每一個Nums1的元素 查詢map 記錄map 的value

class Solution {public int[] nextGreaterElement(int[] nums1, int[] nums2) {// 計算nums2的每一個元素的下一個更大的元素int[] greater = nextGreaterElement(nums2);// 轉(zhuǎn)換為映射  將nums2的每一個元素和greater中的元素進行對應(yīng)Map<Integer,Integer> greaterMap = new HashMap<>();for(int i =0; i < nums2.length; i++){greaterMap.put(nums2[i],greater[i]);// 存儲映射}// nums1 是 nums2的子集  所以根據(jù)greaterMap 可以得到結(jié)果// 從Nums2找到每一個元素int[] res = new int[nums1.length];for(int i = 0; i < nums1.length; i++){res[i] = greaterMap.get(nums1[i]);}return res;}// 計算一個數(shù)組元素的所有單調(diào)棧元素public int[] nextGreaterElement(int[] nums){// 計算單調(diào)棧int n = nums.length;// 存放答案的數(shù)組int[] res = new int[n];Stack<Integer> s = new Stack<>();// 到這往棧存放for(int i = n - 1; i >= 0; i--){// 判斷各自高矮while(!s.isEmpty() && s.peek() <= nums[i]){// 如果棧頂元素 小于等于當(dāng)前 元素 直接將站內(nèi)元素出棧s.pop();}// 存放比當(dāng)前元素大的元素res[i] = s.isEmpty() ? -1 : s.peek();// 如果不是空的  直接存放棧頂元素s.push(nums[i]);}return res;}
}