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;
    		vector<int >res;
    		for (auto i : findNums){
    			if (mark.find(i) != mark.end()){
    		return res;

  • 0
    This post is deleted!

Log in to reply

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