496. 下一个更大元素 I

Problem: 496. 下一个更大元素 I

注意

注意审题: 下面两句话是最重要的

思路

典型的单调栈：

• 使用递增栈

• 需要用map对nums1的值和索引进行映射

• 初始化res为-1

• 注意：单调栈里面存的是nums2的索引

• 对nums2进行一个单调栈的入栈

    - nums2[i] <= nums2[st.top]

        - 符合递增，入栈

    - 否则

        - while(nums2[i] <= nums2[st.top]) 找到了比栈顶元素大的第一个元素

            - 如果是栈顶元素是nums[i]中的元素

                - 计算结果集对应栈顶元素的索引位置的值 为 nums2[i]

                - 弹出

            - 当前索引入栈

• 返回结果集

             

复杂度

时间复杂度:

添加时间复杂度, 示例： $O(n)$

空间复杂度:

添加空间复杂度, 示例： $O(n)$

Code

[]

class Solution {

public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        vector<int> res(nums1.size(), -1);
        if (nums1.size() == 0)
            return res;
        stack<int> st;
        unordered_map<int, int> map;
        st.push(0);
        for (int i = 0; i < nums1.size(); i++)
            map[nums1[i]] = i;
        for (int i = 1; i < nums2.size(); i++) {
            if (nums2[i] <= nums2[st.top()]) {
                st.push(i);
            } else {
                while (!st.empty() && nums2[i] > nums2[st.top()]) {
                    if (map.find(nums2[st.top()]) != map.end()) {
                        res[map[nums2[st.top()]]] = nums2[i];
                    }
                    st.pop();
                }
                st.push(i);
            }
        }
        return res;
    }
};