My O(n) solution using deque


  • 1

    My idea is the same as https://discuss.leetcode.com/topic/77882/my-13ms-o-n-m-solution-using-deque
    using deque

    vector<int> nextGreaterElements(vector<int>& nums) {
    	unordered_map<int, int> mark;
    	deque<int> next;
    	deque<int> index;
    	for (int i = 0; i < nums.size(); i++){
    		while (!next.empty() && nums[i] > next.back()){
    			mark[index.back()] = nums[i];
    			next.pop_back();
    			index.pop_back();
    		}
    		next.push_back(nums[i]);
    		index.push_back(i);
    	}
    	for (int i = 0; i < nums.size(); i++){
    		while (!next.empty() && nums[i] > next.back()){
    			mark[index.back()] = nums[i];
    			next.pop_back();
    			index.pop_back();
    		}
    
    	}
    	vector<int >res(nums.size(), -1);
    	for (int i = 0; i<nums.size(); i++){
    		if (mark.find(i) != mark.end()){
    			res[i] = mark[i];
    		}
    
    	}
    	return res;
    }
    

Log in to reply
 

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