下一个更大元素 I 图解题解

这道题到底在问什么

输入

nums1=[4,1,2], nums2=[2,1,5,6,3,8,4,7]

输出

[7,5,5]

最优解：一步一步想明白

1. 3记住这句，下面每一帧都在演它。
2. 4轮到 nums2[0] = 2，先看它能不能把栈里的小数顶出去。
3. 5没人能再被它弹了（栈顶≥它或栈空），它自己入栈，递减栈结构保持。
4. 6轮到 nums2[1] = 1，先看它能不能把栈里的小数顶出去。
5. 7没人能再被它弹了（栈顶≥它或栈空），它自己入栈，递减栈结构保持。
6. 8轮到 nums2[2] = 5，先看它能不能把栈里的小数顶出去。
7. 9当前数比栈顶大：栈顶等到了它的下一个更大，弹出并记进哈希。继续看还能不能弹。
8. 10当前数比栈顶大：栈顶等到了它的下一个更大，弹出并记进哈希。继续看还能不能弹。
9. 11没人能再被它弹了（栈顶≥它或栈空），它自己入栈，递减栈结构保持。
10. 12轮到 nums2[3] = 6，先看它能不能把栈里的小数顶出去。
11. 13当前数比栈顶大：栈顶等到了它的下一个更大，弹出并记进哈希。继续看还能不能弹。
12. 14没人能再被它弹了（栈顶≥它或栈空），它自己入栈，递减栈结构保持。
13. 15轮到 nums2[4] = 3，先看它能不能把栈里的小数顶出去。
14. 16没人能再被它弹了（栈顶≥它或栈空），它自己入栈，递减栈结构保持。
15. 17轮到 nums2[5] = 8，先看它能不能把栈里的小数顶出去。
16. 18当前数比栈顶大：栈顶等到了它的下一个更大，弹出并记进哈希。继续看还能不能弹。
17. 19当前数比栈顶大：栈顶等到了它的下一个更大，弹出并记进哈希。继续看还能不能弹。
18. 20没人能再被它弹了（栈顶≥它或栈空），它自己入栈，递减栈结构保持。
19. 21轮到 nums2[6] = 4，先看它能不能把栈里的小数顶出去。
20. 22没人能再被它弹了（栈顶≥它或栈空），它自己入栈，递减栈结构保持。
21. 23轮到 nums2[7] = 7，先看它能不能把栈里的小数顶出去。
22. 24当前数比栈顶大：栈顶等到了它的下一个更大，弹出并记进哈希。继续看还能不能弹。
23. 25没人能再被它弹了（栈顶≥它或栈空），它自己入栈，递减栈结构保持。
24. 26扫描结束，栈里残留的 7 右边没有更大的数，它的下一个更大记 -1。
25. 27扫描结束，栈里残留的 8 右边没有更大的数，它的下一个更大记 -1。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

def nextGreaterElement(nums1, nums2):
    greater, stack = {}, []
    for x in nums2:
        while stack and stack[-1] < x:
            greater[stack.pop()] = x   # 栈顶的下一个更大 = x
        stack.append(x)
    return [greater.get(v, -1) for v in nums1]

vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2){
    unordered_map<int,int> g; stack<int> st;
    for(int x : nums2){
        while(!st.empty() && st.top() < x){ g[st.top()] = x; st.pop(); }
        st.push(x);
    }
    vector<int> res;
    for(int v : nums1) res.push_back(g.count(v) ? g[v] : -1);
    return res;
}

public int[] nextGreaterElement(int[] nums1, int[] nums2){
    Map<Integer,Integer> g = new HashMap<>();
    Deque<Integer> st = new ArrayDeque<>();
    for(int x : nums2){
        while(!st.isEmpty() && st.peek() < x) g.put(st.pop(), x);
        st.push(x);
    }
    int[] res = new int[nums1.length];
    for(int i = 0; i < nums1.length; i++) res[i] = g.getOrDefault(nums1[i], -1);
    return res;
}

复杂度

面试官可能追问