刷代随有感(134):单调栈——下一个更大元素I（难点涉及哈希表与单调栈的结合)

单调栈处理的是下标！

题干：

代码：

class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        stack<int>ddst;
        unordered_map<int,int>umap;
        vector<int>res(nums1.size(), -1);
        if(nums1.size() == 0)return res;

        for(int i = 0; i < nums1.size(); i++)
        {
            umap[nums1[i]] = i;
        }

        ddst.push(0);
        for(int i = 1; i < nums2.size(); i++)
        {
            if(nums2[i] <= nums2[ddst.top()]) ddst.push(i);
            else
            {
                while(!ddst.empty() && nums2[i] > nums2[ddst.top()])
                {
                    //结果记录
                    if(umap.count(nums2[ddst.top()]) > 0)
                    {
                        int index = umap[nums2[ddst.top()]];//获取此数组2元素(栈顶)在数组1中下标值
                        res[index] = nums2[i];//将遍历到的(不是栈顶)放入res中
                    }
                    ddst.pop();//记录完成后弹出(持续)
                }
                ddst.push(i);
            }
        }

        return res;
        
    }
};

哈希表的思想：在数组2里找元素而在数组1里面确定，涉及映射关系考虑哈希map。