LeetCode - 496 下一个更大元素 I

题目来源

496. 下一个更大元素 I - 力扣（LeetCode）

题目描述

nums1 中数字 x 的 下一个更大元素 是指 x 在 nums2 中对应位置 右侧 的 第一个 比 x 大的元素。

给你两个 没有重复元素 的数组 nums1 和 nums2 ，下标从 0 开始计数，其中nums1 是 nums2 的子集。

对于每个 0 <= i < nums1.length ，找出满足 nums1[i] == nums2[j] 的下标 j ，并且在 nums2 确定 nums2[j] 的 下一个更大元素 。如果不存在下一个更大元素，那么本次查询的答案是 -1 。

返回一个长度为 nums1.length 的数组 ans 作为答案，满足 ans[i] 是如上所述的 下一个更大元素。

示例1

输入：nums1 = [4,1,2], nums2 = [1,3,4,2].
输出：[-1,3,-1]
解释：nums1 中每个值的下一个更大元素如下所述：
- 4 ，用加粗斜体标识，nums2 = [1,3,4,2]。不存在下一个更大元素，所以答案是 -1 。
- 1 ，用加粗斜体标识，nums2 = [1,3,4,2]。下一个更大元素是 3 。
- 2 ，用加粗斜体标识，nums2 = [1,3,4,2]。不存在下一个更大元素，所以答案是 -1 。

示例2

输入：nums1 = [2,4], nums2 = [1,2,3,4].
输出：[3,-1]
解释：nums1 中每个值的下一个更大元素如下所述：
- 2 ，用加粗斜体标识，nums2 = [1,2,3,4]。下一个更大元素是 3 。
- 4 ，用加粗斜体标识，nums2 = [1,2,3,4]。不存在下一个更大元素，所以答案是 -1 。

提示

• 1 <= nums1.length <= nums2.length <= 1000
• 0 <= nums1[i], nums2[i] <= 104
• nums1和nums2中所有整数 互不相同
• nums1 中的所有整数同样出现在 nums2 中

题目解析

本题可以使用 “单调栈” 解题。

单调栈，即栈内（从栈底到栈顶）元素呈现单调递减或单调递增性质。

本题要求每个元素的下一个更大元素，则可以使用单调递减栈。

具体应用逻辑如下：

• 遍历 nums 数组的每个元素 num，尝试压入 stack，但是压栈前，需要和 stack.top 栈顶元素比较大小：

1. 若 stack 为空 或者 num ≤ stack.top，则 num 压栈后，不会破坏 stack 的（非严格）单调递减性质，此时 num 可以直接压栈。
2. 若 num > stack.top，则 num 压栈后，会破坏 stack 的单调递减性质，此时我们应该将 stack.top 弹出。
   
   stack.top 弹栈的同时，意味着 stack.top 元素找到了它的下一个更大元素（即：num）。
   
   stack.top 弹栈完成后，此时 num 还需要继续和新的栈顶元素进行比较大小，循环上面逻辑，直到 stack 为空或者 num ≤ stack.top，才能将 num 压入 stack。

C算法源码

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* nextGreaterElement(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize) {
    int nextBigger[10001];
    for (int i = 0; i <= 10000; i++) {
        nextBigger[i] = -1;
    }

    // （非严格）单调递减栈, 即栈底(索引0位置) 到栈顶（索引stack_size-1位置）的元素是(非严格)单调递减的
    int stack[1000];
    int stack_size = 0;

    // 遍历 nums2 的元素 nums2[i]
    for (int i = 0; i < nums2Size; i++) {
        // 若 stack 非空 且 nums2[i] > stack.top, 则此时 nums2[i] 压栈会破坏 stack 的（非严格）单调递减性质
        while (stack_size > 0 && nums2[i] > stack[stack_size - 1]) {
            // 因此我们需要将 stack.top 弹栈, 弹栈的同时，我们也找到了 stack.top 的下一个更大元素（即为：nums2[i]）
            nextBigger[stack[--stack_size]] = nums2[i];
        }

        // 当 stack 为空 或 nums2[i] ≤ stack.top，则此时 nums2[i] 压栈不会破坏 stack 的（非严格）单调递减性质
        stack[stack_size++] = nums2[i];
    }

    int* ans = (int*) malloc(sizeof(int) * nums1Size);
    for (int i = 0; i < nums1Size; i++) {
        ans[i] = nextBigger[nums1[i]];
    }

    *returnSize = nums1Size;

    return ans;
}

C++算法源码

class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        map<int, int> nextBigger;

        // （非严格）单调递减栈, 即栈底到栈顶的元素是(非严格)单调递减的
        deque<int> stack;

        // 遍历 nums2 的元素 num
        for (int num : nums2) {
            // 若 stack 非空 且 num > stack.top, 则此时 num 压栈会破坏 stack 的（非严格）单调递减性质
            while (!stack.empty() && num > stack.back()) {
                // 因此我们需要将 stack.top 弹栈, 弹栈的同时，我们也找到了 stack.top 的下一个更大元素（即为：num）
                nextBigger[stack.back()] = num;
                stack.pop_back();
            }

            // 当 stack 为空 或 num ≤ stack.top，则此时 num 压栈不会破坏 stack 的（非严格）单调递减性质
            stack.push_back(num);
        }

        vector<int> ans(nums1.size());
        for (int i = 0; i < nums1.size(); i++) {
            if (nextBigger.find(nums1[i]) != nextBigger.end()) {
                ans[i] = nextBigger[nums1[i]];
            } else {
                ans[i] = -1;
            }
        }

        return ans;
    }
};

JS算法源码

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var nextGreaterElement = function (nums1, nums2) {
    const nextBigger = {};

    // （非严格）单调递减栈, 即栈底到栈顶的元素是(非严格)单调递减的
    const stack = [];
    
    // 遍历 nums2 的元素 num
    for (let num of nums2) {
        // 若 stack 非空 且 num > stack.top, 则此时 num 压栈会破坏 stack 的（非严格）单调递减性质
        while (stack.length > 0 && num > stack.at(-1)) {
            // 因此我们需要将 stack.top 弹栈, 弹栈的同时，我们也找到了 stack.top 的下一个更大元素（即为：num）
            nextBigger[stack.pop()] = num;
        }

        // 当 stack 为空 或 num ≤ stack.top，则此时 num 压栈不会破坏 stack 的（非严格）单调递减性质
        stack.push(num);
    }

    const ans = new Array(nums1.length);
    for (let i = 0; i < nums1.length; i++) {
        ans[i] = nextBigger[nums1[i]] ?? -1;
    }

    return ans;
};

Java算法源码

class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        HashMap<Integer, Integer> nextBigger = new HashMap<>();

        // （非严格）单调递减栈, 即栈底到栈顶的元素是(非严格)单调递减的
        ArrayDeque<Integer> stack = new ArrayDeque<>();

        // 遍历 nums2 的元素 num
        for (int num : nums2) {
            // 若 stack 非空 且 num > stack.top, 则此时 num 压栈会破坏 stack 的（非严格）单调递减性质
            while (!stack.isEmpty() && num > stack.peek()) {
                // 因此我们需要将 stack.top 弹栈, 弹栈的同时，我们也找到了 stack.top 的下一个更大元素（即为：num）
                nextBigger.put(stack.pop(), num);
            }

            // 当 stack 为空 或 num ≤ stack.top，则此时 num 压栈不会破坏 stack 的（非严格）单调递减性质
            stack.push(num);
        }

        int[] ans = new int[nums1.length];
        for (int i = 0; i < nums1.length; i++) {
            ans[i] = nextBigger.getOrDefault(nums1[i], -1);
        }

        return ans;
    }
}

Python算法源码

class Solution(object):
    def nextGreaterElement(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: List[int]
        """
        nextBigger = {}

        # （非严格）单调递减栈, 即栈底到栈顶的元素是(非严格)单调递减的
        stack = []

        # 遍历 nums2 的元素 num
        for num in nums2:
            # 若 stack 非空 且 num > stack.top, 则此时 num 压栈会破坏 stack 的（非严格）单调递减性质
            while stack and num > stack[-1]:
                # 因此我们需要将 stack.top 弹栈, 弹栈的同时，我们也找到了 stack.top 的下一个更大元素（即为：num）
                nextBigger[stack.pop()] = num
            
            # 当 stack 为空 或 num ≤ stack.top，则此时 num 压栈不会破坏 stack 的（非严格）单调递减性质
            stack.append(num)
        
        ans = []
        for num in nums1:
            ans.append(nextBigger.get(num, -1))
        
        return ans