cpp solution using map


  • 0
    H

    We know the map is implemented by using red-black tree,so the last element is the biggest one in this time.

    class Solution {
    public:
    	vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    		if (nums.empty())
    			return vector<int>();
    		map<int, int> mp;
    		vector<int> ans;
    		for (int i = 0; i < k; i++) {
    			if (mp.find(nums[i]) == mp.end()) {
    				mp[nums[i]] = 1;
    			}
    			else
    				mp[nums[i]]++;
    		}
    		auto p = mp.end();
    		p--;
    		ans.push_back(p->first);
    		for (int i = 0, j = k; j < nums.size(); i++, j++) {
    			mp[nums[i]]--;
    			if (mp[nums[i]] == 0)//erase it if this element doesn't exit in this time
    				mp.erase(nums[i]);
    			if (mp.find(nums[j]) == mp.end()) {
    				mp[nums[j]] = 1;
    			}
    			else {
    				mp[nums[j]]++;
    			}
    			p = mp.end();
    			p--;//get the max element 
    			ans.push_back(p->first);
    		}
    		return ans;
    	}
    };
    

Log in to reply
 

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