My 13ms O(n+m) solution using deque


  • 0

    We can use the monotone decreasing deque(Actually, in this solution, we can also use stack).
    If the back of the deque is lager than nums[i], push nums[i] in the deque's back.
    If the back of the deque is smaller than nums[i], it means the Next Greater Element of the back of deque is nums[i]. Then pop it out, until the back of the deque is lager than nums[i];

    	vector<int> nextGreaterElement(vector<int>& findNums, vector<int>& nums) {
    		unordered_map<int, int> mark;
    		deque<int> next;
    		for (auto i : nums){
    			while (!next.empty() && i > next.back()){
    				mark[next.back()] = i;
    				next.pop_back();
    			}
    			next.push_back(i);
    		}
    		vector<int >res;
    		for (auto i : findNums){
    			if (mark.find(i) != mark.end()){
    				res.push_back(mark[i]);
    			}
    			else{
    				res.push_back(-1);
    			}
    		}
    		return res;
    	}
    

  • 0
    S
    This post is deleted!

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.