C语言重构【496】下一个更大元素 I

待我称王封你为后i 2022-11-07 04:15 140阅读 0赞

### 文章目录 ###

*   *   *   *  所有题目源代码：\[Git地址\](https://github.com/ch98road/leetcode)
             *  题目
             *  方案：
             *   *  复杂度计算

#### 所有题目源代码：[Git地址][Git] ####

#### 题目 ####

给你两个 没有重复元素 的数组 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] <= 104
    nums1和nums2中所有整数 互不相同
    nums1 中的所有整数同样出现在 nums2 中

#### 方案： ####

*  单调栈的应用：[个人理解][Link 1]

class Solution
    { 
    public:
        vector<int> nextGreaterElement(vector<int> &nums1, vector<int> &nums2)
        { 
            int len1 = nums1.size();
            int len2 = nums2.size();
    
            map<int, int> m;
            stack<int> s;
            vector<int> res(len1, -1);
            //用map记录一下每个数的位置，便于后面寻找
            for (int i = 0; i < len1; i++)
            { 
                m[nums1[i]] = i;
            }
            s.push(nums2[0]);
            for (int i = 1; i < len2; i++)
            { 
                //单调栈思想
                while ((!s.empty()) && s.top() < nums2[i])
                { 
                    if (m.find(s.top()) != m.end())
                    { 
                        res[m[s.top()]] = nums2[i];
                    }
                    s.pop();
                }
                s.push(nums2[i]);
            }
            return res;
        }
    };

##### 复杂度计算 #####

*  时间复杂度：O(n)
 *  空间复杂度：O(n)

[Git]: https://github.com/ch98road/leetcode
[Link 1]: https://blog.csdn.net/symuamua/article/details/114649796