【leetcode刷題】51.下一個更大元素 I—

?歡迎訂閱《leetcode》專欄，每日一題，每天進步?

演算法不行，現在語文也不行了，我哭了，你們呢？

——leetcode此題熱評

前言

哈嘍，大家好，我是一條，

糊涂演算法，難得糊涂

《糊涂演算法》專欄上線倒計時——7天

Question

496. 下一個更大元素 I

難度：簡單

給你兩個沒有重復元素的陣列 nums1 和 nums2 ，其中nums1 是 nums2 的子集，

請你找出 nums1 中每個元素在 nums2 中的下一個比其大的值，

nums1 中數字 x 的下一個更大元素是指 x 在 nums2 中對應位置的右邊的第一個比 x 大的元素，如果不存在，對應位置輸出 -1 ，

示例 1:
輸入: nums1 = [4,1,2], nums2 = [1,3,4,2].
輸出: [-1,3,-1]
解釋:
   對于 num1 中的數字 4 ，你無法在第二個陣列中找到下一個更大的數字，因此輸出 -1 ，
   對于 num1 中的數字 1 ，第二個陣列中數字1右邊的下一個較大數字是 3 ，
   對于 num1 中的數字 2 ，第二個陣列中沒有下一個更大的數字，因此輸出 -1 ，
示例 2:
輸入: nums1 = [2,4], nums2 = [1,2,3,4].
輸出: [3,-1]
解釋:
   對于 num1 中的數字 2 ，第二個陣列中的下一個較大數字是 3 ，
   對于 num1 中的數字 4 ，第二個陣列中沒有下一個更大的數字，因此輸出 -1 ，
提示：
1 <= nums1.length <= nums2.length <= 1000
0 <= nums1[i], nums2[i] <= 104
nums1和nums2中所有整數 互不相同
nums1 中的所有整數同樣出現在 nums2 中

Solution

注意一句話其中nums1 是 nums2 的子集，，這樣我們只需要處理好num2存入hashmap即可，

如何處理nums2？

單調堆疊

元素入堆疊
如果下一個大于堆疊頂，堆疊頂出堆疊
遍歷nums1

Code

所有leetcode代碼已同步至github

歡迎star

/**
 * @author 一條coding
 */
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

public class Solution {

    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<>();
        // 先處理 nums2，把對應關系存入哈希表
        for (int i = 0; i < len2; i++) {
            while (!stack.isEmpty() && stack.peekLast() < nums2[i]) {
                map.put(stack.removeLast(), nums2[i]);
            }
            stack.addLast(nums2[i]);
        }

        // 遍歷 nums1 得到結果集
        int[] res = new int[len1];
        for (int i = 0; i < len1; i++) {
            res[i] = map.getOrDefault(nums1[i], -1);
        }
        return res;
    }
}