【leetcode】496. Next Greater Element I

problem:

496. Next Greater Element I

题意：求集合中每个数字在原数组中右边第一个较大的数字。

solution1: 暴力搜索；

class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        vector<int> ans;
        for(int i=0; i<nums1.size(); i++)
        {
            int j = 0, k = 0;
            for(; j<nums2.size(); j++)
            {
                if(nums1[i]==nums2[j]) break;
            }
            int flag = false;
            for(k=j+1; k<nums2.size(); k++)
            {
                if(nums2[j] < nums2[k]) 
                {
                    flag = true;
                    ans.push_back(nums2[k]);
                    break;
                }
            }
            if(!flag) ans.push_back(-1);
            
        }
        return ans;
        
    }
};

solution2: 使用元素映射map确定子集元素的位置(推荐);

class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        vector<int> ans(nums1.size());
        map<int, int> mymap;
        for(int i=0; i<nums2.size(); i++)
        {
            mymap[nums2[i]] = i;
        }
        for(int i=0; i<nums1.size(); i++)
        {
            ans[i] = -1;
            //int start = mymap[nums1[i]];
            for(int j=mymap[nums1[i]]+1; j<nums2.size(); j++)
            {
                if(nums1[i] < nums2[j]) 
                {
                    ans[i] = nums2[j];
                    break;
                }
                
            }
            
        }
        return ans;
        
    }
};

参考

1. leetcode_496_Next Greater Element I;

2. GrandYang;

完