496. 下一个更大元素 I

题目链接：496. 下一个更大元素 I

方法一：模拟 + 哈希表

解题思路

通过哈希表存储，\(nums\) 数组中元素对应的坐标，元素->坐标。
然后模拟查找过程。

代码

class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        unordered_map<int, int> index;
        int n1 = nums1.size(), n2 = nums2.size();
        for (int i = 0; i < n2; i ++ ) index[nums2[i]] = i;
        vector<int> ans;
        for (int i = 0; i < n1; i ++ ) {
            int x = nums1[i];
            int x_index = index[x];
            int j; bool flag = false;
            for (j = x_index + 1; j < n2; j ++ ){
                if (nums2[j] > x) {
                    flag = true;
                    break;
                }
            }
            if (flag) ans.emplace_back(nums2[j]);
            else ans.emplace_back(-1);
        }
        return ans;
    }
};

复杂度分析

时间复杂度：\(O(n1 * n2)\)，\(n1\) 和 \(n2\) 分别为 \(nums1\) 和 \(nums2\) 数组的长度；
空间复杂度：\(O(n2)\)。

方法二：单调栈

解题思路

单调栈解决 Next Greater Number 一类问题

代码

class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        int index[10001]; // index[i]，表示数字i，在nums2数组中下一个更大数字的下标
        vector<int> ans;
        stack<int> stk; // 存放下标
        for (int i = nums2.size() - 1; i >= 0; i -- ) {
            while (!stk.empty() && nums2[stk.top()] <= nums2[i]) stk.pop();
            index[nums2[i]] = stk.empty() ? -1 : stk.top();
            stk.push(i);
        }
        for (int i = 0; i < nums1.size(); i ++ ){
            if (index[nums1[i]] == -1) ans.emplace_back(-1);
            else ans.emplace_back(nums2[index[nums1[i]]]);
        }
        return ans;
    }
};

复杂度分析

时间复杂度：\(O(n1 + n2)\)，\(n1\) 和 \(n2\) 分别为 \(nums1\) 和 \(nums2\) 数组的长度；
空间复杂度：\(O(n)\)，\(n\) 为 \(index\) 数组长度。