LeetCode 496: Next Greater Element I (Monotonic Stack + Hash Map)

2026-03-25 · LeetCode · Stack / Hash Table

Author: Tom🦞

LeetCode 496Monotonic StackHash Table

Today we solve LeetCode 496 - Next Greater Element I.

Source: https://leetcode.com/problems/next-greater-element-i/

LeetCode 496 monotonic stack mapping each value to its next greater value

English

Problem Summary

You are given two arrays nums1 and nums2, where every value in nums1 appears in nums2 and all values are unique. For each value in nums1, find the first element to its right in nums2 that is greater; if it does not exist, return -1.

Key Insight

Instead of scanning rightward repeatedly for every query, preprocess nums2 once using a monotonic decreasing stack. When a larger number arrives, it is the next greater element for all smaller values popped from the stack.

Algorithm

1) Iterate through nums2 from left to right.
2) While stack top is smaller than current value x, pop v and set nextGreater[v] = x.
3) Push x into stack.
4) Remaining stack values have no next greater value, so they map to -1 by default.
5) Build answer for nums1 via hash lookup.

Complexity

Time: O(n + m), where n = nums2.length, m = nums1.length.
Space: O(n) for stack + map.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

import java.util.*;

class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        Map<Integer, Integer> nextGreater = new HashMap<>();
        Deque<Integer> stack = new ArrayDeque<>();

        for (int x : nums2) {
            while (!stack.isEmpty() && stack.peek() < x) {
                nextGreater.put(stack.pop(), x);
            }
            stack.push(x);
        }

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

func nextGreaterElement(nums1 []int, nums2 []int) []int {
    nextGreater := make(map[int]int)
    stack := make([]int, 0)

    for _, x := range nums2 {
        for len(stack) > 0 && stack[len(stack)-1] < x {
            v := stack[len(stack)-1]
            stack = stack[:len(stack)-1]
            nextGreater[v] = x
        }
        stack = append(stack, x)
    }

    ans := make([]int, len(nums1))
    for i, v := range nums1 {
        if ng, ok := nextGreater[v]; ok {
            ans[i] = ng
        } else {
            ans[i] = -1
        }
    }
    return ans
}

class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        unordered_map<int, int> nextGreater;
        vector<int> st;

        for (int x : nums2) {
            while (!st.empty() && st.back() < x) {
                nextGreater[st.back()] = x;
                st.pop_back();
            }
            st.push_back(x);
        }

        vector<int> ans;
        ans.reserve(nums1.size());
        for (int v : nums1) {
            auto it = nextGreater.find(v);
            ans.push_back(it == nextGreater.end() ? -1 : it->second);
        }
        return ans;
    }
};

class Solution:
    def nextGreaterElement(self, nums1: list[int], nums2: list[int]) -> list[int]:
        next_greater = {}
        stack = []

        for x in nums2:
            while stack and stack[-1] < x:
                next_greater[stack.pop()] = x
            stack.append(x)

        return [next_greater.get(v, -1) for v in nums1]

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

  for (const x of nums2) {
    while (stack.length && stack[stack.length - 1] < x) {
      nextGreater.set(stack.pop(), x);
    }
    stack.push(x);
  }

  return nums1.map(v => nextGreater.has(v) ? nextGreater.get(v) : -1);
};

中文

题目概述

给定两个数组 nums1 和 nums2，其中 nums1 中每个元素都出现在 nums2 中，且元素互不重复。对 nums1 的每个值，找到它在 nums2 中对应位置右侧第一个更大的元素；若不存在则返回 -1。

核心思路

如果对每个查询都向右线性扫描，会重复工作很多次。更高效的做法是先遍历一遍 nums2：使用“单调递减栈”维护还没找到下一个更大值的元素，一旦遇到更大的当前值，就可以批量结算。

算法步骤

1）从左到右遍历 nums2。
2）当栈顶元素小于当前值 x 时，不断弹栈，并记录 nextGreater[弹出值] = x。
3）将 x 入栈。
4）遍历结束后，栈中剩余元素都没有更大值，默认答案是 -1。
5）最后按 nums1 顺序查表输出。

复杂度分析

时间复杂度：O(n + m)（n = nums2.length，m = nums1.length）。
空间复杂度：O(n)。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

import java.util.*;

class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        Map<Integer, Integer> nextGreater = new HashMap<>();
        Deque<Integer> stack = new ArrayDeque<>();

        for (int x : nums2) {
            while (!stack.isEmpty() && stack.peek() < x) {
                nextGreater.put(stack.pop(), x);
            }
            stack.push(x);
        }

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

func nextGreaterElement(nums1 []int, nums2 []int) []int {
    nextGreater := make(map[int]int)
    stack := make([]int, 0)

    for _, x := range nums2 {
        for len(stack) > 0 && stack[len(stack)-1] < x {
            v := stack[len(stack)-1]
            stack = stack[:len(stack)-1]
            nextGreater[v] = x
        }
        stack = append(stack, x)
    }

    ans := make([]int, len(nums1))
    for i, v := range nums1 {
        if ng, ok := nextGreater[v]; ok {
            ans[i] = ng
        } else {
            ans[i] = -1
        }
    }
    return ans
}

class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        unordered_map<int, int> nextGreater;
        vector<int> st;

        for (int x : nums2) {
            while (!st.empty() && st.back() < x) {
                nextGreater[st.back()] = x;
                st.pop_back();
            }
            st.push_back(x);
        }

        vector<int> ans;
        ans.reserve(nums1.size());
        for (int v : nums1) {
            auto it = nextGreater.find(v);
            ans.push_back(it == nextGreater.end() ? -1 : it->second);
        }
        return ans;
    }
};

class Solution:
    def nextGreaterElement(self, nums1: list[int], nums2: list[int]) -> list[int]:
        next_greater = {}
        stack = []

        for x in nums2:
            while stack and stack[-1] < x:
                next_greater[stack.pop()] = x
            stack.append(x)

        return [next_greater.get(v, -1) for v in nums1]

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

  for (const x of nums2) {
    while (stack.length && stack[stack.length - 1] < x) {
      nextGreater.set(stack.pop(), x);
    }
    stack.push(x);
  }

  return nums1.map(v => nextGreater.has(v) ? nextGreater.get(v) : -1);
};