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] <= 10^4
nums1和nums2中所有整数互不相同
nums1 中的所有整数同样出现在 nums2 中

思路

做本题之前，建议先做一下739. 每日温度

在739. 每日温度中是求每个元素下一个比当前元素大的元素的位置。

本题则是说nums1 是 nums2的子集，找nums1中的元素在nums2中下一个比当前元素大的元素。

看上去和739. 每日温度就如出一辙了。

几乎是一样的，但是这么绕了一下，其实还上升了一点难度。

需要对单调栈使用的更熟练一些，才能顺利的把本题写出来。

从题目示例中我们可以看出最后是要求nums1的每个元素在nums2中下一个比当前元素大的元素，那么就要定义一个和nums1一样大小的数组result来存放结果。

一些同学可能看到两个数组都已经懵了，不知道要定一个一个多大的result数组来存放结果了。

这么定义这个result数组初始化应该为多少呢？

题目说如果不存在对应位置就输出 -1 ，所以result数组如果某位置没有被赋值，那么就应该是是-1，所以就初始化为-1。

在遍历nums2的过程中，我们要判断nums2[i]是否在nums1中出现过，因为最后是要根据nums1元素的下标来更新result数组。

注意题目中说是两个没有重复元素的数组 nums1 和 nums2。

没有重复元素，我们就可以用map来做映射了。根据数值快速找到下标，还可以判断nums2[i]是否在nums1中出现过。

C++中，当我们要使用集合来解决哈希问题的时候，优先使用unordered_set，因为它的查询和增删效率是最优的。我在关于哈希表，你该了解这些！中也做了详细的解释。

那么预处理代码如下:

C++
unordered_map<int, int> umap; // key:下标元素，value：下标
for (int i = 0; i < nums1.size(); i++) {
    umap[nums1[i]] = i;
}

使用单调栈，首先要想单调栈是从大到小还是从小到大。

本题和739. 每日温度是一样的。

栈头到栈底的顺序，要从小到大，也就是保持栈里的元素为递增顺序。只要保持递增，才能找到右边第一个比自己大的元素。

可能这里有一些同学不理解，那么可以自己尝试一下用递减栈，能不能求出来。其实递减栈就是求右边第一个比自己小的元素了。

接下来就要分析如下三种情况，一定要分析清楚。

情况一：当前遍历的元素T[i]小于栈顶元素T[st.top()]的情况

此时满足递增栈（栈头到栈底的顺序），所以直接入栈。

情况二：当前遍历的元素T[i]等于栈顶元素T[st.top()]的情况

如果相等的话，依然直接入栈，因为我们要求的是右边第一个比自己大的元素，而不是大于等于！

情况三：当前遍历的元素T[i]大于栈顶元素T[st.top()]的情况

此时如果入栈就不满足递增栈了，这也是找到右边第一个比自己大的元素的时候。

判断栈顶元素是否在nums1里出现过，（注意栈里的元素是nums2的元素），如果出现过，开始记录结果。

记录结果这块逻辑有一点小绕，要清楚，此时栈顶元素在nums2数组中右面第一个大的元素是nums2[i]（即当前遍历元素）。

代码如下：

C++
while (!st.empty() && nums2[i] > nums2[st.top()]) {
    if (umap.count(nums2[st.top()]) > 0) { // 看map里是否存在这个元素
        int index = umap[nums2[st.top()]]; // 根据map找到nums2[st.top()] 在 nums1中的下标
        result[index] = nums2[i];
    }
    st.pop();
}
st.push(i);

以上分析完毕，C++代码如下：（其实本题代码和739. 每日温度是基本差不多的）

C++
// 版本一
class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        stack<int> st;
        vector<int> result(nums1.size(), -1);
        if (nums1.size() == 0) return result;

        unordered_map<int, int> umap; // key:下标元素，value：下标
        for (int i = 0; i < nums1.size(); i++) {
            umap[nums1[i]] = i;
        }
        st.push(0);
        for (int i = 1; i < nums2.size(); i++) {
            if (nums2[i] < nums2[st.top()]) {           // 情况一
                st.push(i);
            } else if (nums2[i] == nums2[st.top()]) {   // 情况二
                st.push(i);
            } else {                                    // 情况三
                while (!st.empty() && nums2[i] > nums2[st.top()]) {
                    if (umap.count(nums2[st.top()]) > 0) { // 看map里是否存在这个元素
                        int index = umap[nums2[st.top()]]; // 根据map找到nums2[st.top()] 在 nums1中的下标
                        result[index] = nums2[i];
                    }
                    st.pop();
                }
                st.push(i);
            }
        }
        return result;
    }
};

针对版本一，进行代码精简后，代码如下：

C++
// 版本二
class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        stack<int> st;
        vector<int> result(nums1.size(), -1);
        if (nums1.size() == 0) return result;

        unordered_map<int, int> umap; // key:下标元素，value：下标
        for (int i = 0; i < nums1.size(); i++) {
            umap[nums1[i]] = i;
        }
        st.push(0);
        for (int i = 1; i < nums2.size(); i++) {
            while (!st.empty() && nums2[i] > nums2[st.top()]) {
                if (umap.count(nums2[st.top()]) > 0) { // 看map里是否存在这个元素
                    int index = umap[nums2[st.top()]]; // 根据map找到nums2[st.top()] 在 nums1中的下标
                    result[index] = nums2[i];
                }
                st.pop();
            }
            st.push(i);
        }
        return result;
    }
};

精简的代码是直接把情况一二三都合并到了一起，其实这种代码精简是精简，但思路不是很清晰。

建议大家把情况一二三想清楚了，先写出版本一的代码，然后在其基础上在做精简！

其他语言版本

C
/* 先用单调栈的方法计算出结果，再根据nums1中的元素去查找对应的结果 */
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* nextGreaterElement(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize) {

    /* stcak */
    int top = -1;
    int stack_len = nums2Size;
    int stack[stack_len];
    //memset(stack, 0x00, sizeof(stack));

    /* nums2 result */
    int* result_nums2 = (int *)malloc(sizeof(int) * nums2Size);
    //memset(result_nums2, 0x00, sizeof(int) * nums2Size);

    /* result */
    int* result = (int *)malloc(sizeof(int) * nums1Size);
    //memset(result, 0x00, sizeof(int) * nums1Size);
    *returnSize = nums1Size;

    /* init */
    stack[++top] = 0; /* stack loaded with array subscripts */

    for (int i = 0; i < nums2Size; i++) {
        result_nums2[i] = -1;
    }

    /* get the result_nums2 */
    for (int i = 1; i < nums2Size; i++) {
        if (nums2[i] <= nums2[stack[top]]) {
            stack[++top] = i; /* push */
        } else {
            while ((top >= 0) && (nums2[i] > nums2[stack[top]])) {
                result_nums2[stack[top]] = nums2[i];
                top--; /* pop */
            }
            stack[++top] = i;
        }
    }

    /* get the result */
    for (int i = 0; i < nums1Size; i++) {
        for (int j = 0; j < nums2Size; j++) {
            if (nums1[i] == nums2[j]) {
                result[i] = result_nums2[j];
            }
        }
    }
    return result;
}

Java
class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        Stack<Integer> temp = new Stack<>();
        int[] res = new int[nums1.length];
        Arrays.fill(res,-1);
        HashMap<Integer, Integer> hashMap = new HashMap<>();
        for (int i = 0 ; i< nums1.length ; i++){
            hashMap.put(nums1[i],i);
        }
        temp.add(0);
        for (int i = 1; i < nums2.length; i++) {
            if (nums2[i] <= nums2[temp.peek()]) {
                temp.add(i);
            } else {
                while (!temp.isEmpty() && nums2[temp.peek()] < nums2[i]) {
                    if (hashMap.containsKey(nums2[temp.peek()])){
                        Integer index = hashMap.get(nums2[temp.peek()]);
                        res[index] = nums2[i];
                    }
                    temp.pop();
                }
                temp.add(i);
            }
        }

        return res;
    }
}

// 版本2
class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums1.length; i++) {
            map.put(nums1[i], i);
        }

        int[] res = new int[nums1.length];
        Stack<Integer> stack = new Stack<>();
        Arrays.fill(res, -1);

        for (int i = 0; i < nums2.length; i++) {
            while (!stack.isEmpty() && nums2[stack.peek()] < nums2[i]) {
                int pre = nums2[stack.pop()];
                if (map.containsKey(pre)) {
                    res[map.get(pre)] = nums2[i];
                }
            }
            stack.push(i);
        }

        return res;
    }
}

Python
# 版本一
class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        result = [-1]*len(nums1)
        stack = [0]
        for i in range(1,len(nums2)):
            # 情况一情况二
            if nums2[i]<=nums2[stack[-1]]:
                stack.append(i)
            # 情况三
            else:
                while len(stack)!=0 and nums2[i]>nums2[stack[-1]]:
                    if nums2[stack[-1]] in nums1:
                        index = nums1.index(nums2[stack[-1]])
                        result[index]=nums2[i]
                    stack.pop()
                stack.append(i)
        return result

# 版本二
class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        stack = []
        # 创建答案数组
        ans = [-1] * len(nums1)
        for i in range(len(nums2)):
            while len(stack) > 0 and nums2[i] > nums2[stack[-1]]:
                # 判断 num1 是否有 nums2[stack[-1]]。如果没有这个判断会出现指针异常
                if nums2[stack[-1]] in nums1:
                    # 锁定 num1 检索的 index
                    index = nums1.index(nums2[stack[-1]])
                    # 更新答案数组
                    ans[index] = nums2[i]
                # 弹出小元素
                # 这个代码一定要放在 if 外面。否则单调栈的逻辑就不成立了
                stack.pop()
            stack.append(i)
        return ans

未精简版本

Go
func nextGreaterElement(nums1 []int, nums2 []int) []int {
    res := make([]int, len(nums1))
    for i := range res { res[i] = -1 }
    m := make(map[int]int, len(nums1))
    for k, v := range nums1 { m[v] = k }

    stack := []int{0}
    for i := 1; i < len(nums2); i++ {
        top := stack[len(stack)-1]
        if nums2[i] < nums2[top] {
            stack = append(stack, i)
        } else if nums2[i] == nums2[top] {
            stack = append(stack, i)
        } else {
            for len(stack) != 0 && nums2[i] > nums2[top] {
                if v, ok := m[nums2[top]]; ok {
                    res[v] = nums2[i]
                }
                stack = stack[:len(stack)-1]
                if len(stack) != 0 {
                    top = stack[len(stack)-1]
                }
            }
            stack = append(stack, i)
        }
    }
    return res
}

精简版本

Go
func nextGreaterElement(nums1 []int, nums2 []int) []int {
    res := make([]int, len(nums1))
    for i:= range res {
        res[i] = -1
    }
    mp := map[int]int{}
    for i,v := range nums1 {
        mp[v] = i
    }
    // 单调栈
    stack := []int{}
    stack = append(stack,0)

    for i:=1; i<len(nums2); i++ {
        for len(stack) >0 && nums2[i] > nums2[stack[len(stack)-1]] {

            top := stack[len(stack)-1]

            if _, ok := mp[nums2[top]]; ok {    // 看map里是否存在这个元素
                index := mp[nums2[top]];        // 根据map找到nums2[top] 在 nums1中的下标
                res[index] = nums2[i]
            }

            stack = stack[:len(stack)-1]        // 出栈
        }
        stack = append(stack, i)
    }
    return res
}

JavaScript
var nextGreaterElement = function (nums1, nums2) {
  let stack = [];
  let map = new Map();
  for (let i = 0; i < nums2.length; i++) {
    while (stack.length && nums2[i] > nums2[stack[stack.length - 1]]) {
      let index = stack.pop();
      map.set(nums2[index], nums2[i]);
    }
    stack.push(i);
  }

  let res = [];
  for (let j = 0; j < nums1.length; j++) {
    res[j] = map.get(nums1[j]) || -1;
  }

  return res;
};

TypeScript
function nextGreaterElement(nums1: number[], nums2: number[]): number[] {
    const resArr: number[] = new Array(nums1.length).fill(-1);
    const stack: number[] = [];
    const helperMap: Map<number, number> = new Map();
    nums1.forEach((num, index) => {
        helperMap.set(num, index);
    })
    stack.push(0);
    for (let i = 1, length = nums2.length; i < length; i++) {
        let top = stack[stack.length - 1];
        while (stack.length > 0 && nums2[top] < nums2[i]) {
            let index = helperMap.get(nums2[top]);
            if (index !== undefined) {
                resArr[index] = nums2[i];
            }
            stack.pop();
            top = stack[stack.length - 1];
        }
        if (helperMap.get(nums2[i]) !== undefined) {
            stack.push(i);
        }
    }
    return resArr;
};

Rust
use std::collections::HashMap;
impl Solution {
    pub fn next_greater_element(nums1: Vec<i32>, nums2: Vec<i32>) -> Vec<i32> {
        let (mut res, mut map) = (vec![-1; nums1.len()], HashMap::new());
        if nums1.is_empty() {
            return res;
        }

        nums1.into_iter().enumerate().for_each(|(v, k)| {
            map.insert(k, v);
        });

        let mut stack = vec![];
        for (i, &value) in nums2.iter().enumerate() {
            while let Some(&top) = stack.last() {
                if value <= nums2[top] {
                    break;
                }
                let stacked_index = stack.pop().unwrap();
                if let Some(&mapped_index) = map.get(&nums2[stacked_index]) {
                    res[mapped_index] = value;
                }
            }
            stack.push(i);
        }

        res
    }
}

思路​

其他语言版本​

思路

其他语言版本