LeetCode

LeetCode-496 下一个更大元素I

nkul · 7月11日 · 2020年 1662次已读

对nums2而言,从后往前看,即在已遍历的数中找最近最大数,典型的单调栈应用!

本题比较特殊点为需要用map记录nums1数组的数和下标,以便形成返回数组。

class Solution {
public:
    vector nextGreaterElement(vector& nums1, vector& nums2) {
        int l1 = nums1.size();
        int l2 = nums2.size();
        //返回值
        vector res(l1,0);
        if(l2==0) return res;
        //用map记录数组1的元素及下标key:元素,val:下标
        unordered_mapheap;
        for(int i=0;i=0;i--){
            //下面四行都是固定套路
            int tmp;
            while(tt>=0 && stk[tt]<= nums2[i]) tt--;
            if(tt>=0) tmp = stk[tt];
            else tmp = -1;
            stk[++tt] = nums2[i];
            //这里结合map构造返回数组
            if(heap[nums2[i]]>0){
                res[heap[nums2[i]]-1] = tmp;
            }
        }
        return res;
    }
};


0 条回应

必须 注册 为本站用户, 登录 后才可以发表评论!