leetcode 239. Sliding Window Maximum

电玩女神 2022-08-20 15:15 12阅读 0赞

Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.  
  
  
For example,  
Given nums = \[1,3,-1,-3,5,3,6,7\], and k = 3.  
  
  
Window position                Max  
\---------------               -----  
\[1  3  -1\] -3  5  3  6  7       3  
 1 \[3  -1  -3\] 5  3  6  7       3  
 1  3 \[-1  -3  5\] 3  6  7       5  
 1  3  -1 \[-3  5  3\] 6  7       5  
 1  3  -1  -3 \[5  3  6\] 7       6  
 1  3  -1  -3  5 \[3  6  7\]      7  
Therefore, return the max sliding window as \[3,3,5,5,6,7\].  
  
  
Note:   
You may assume k is always valid, ie: 1 ≤ k ≤ input array's size for non-empty array.  
  
  
Follow up:  
Could you solve it in linear time?

#include "stdafx.h"
    #include<vector>
    #include<set>
    #include<map>
    #include <functional> 
    #include<iostream>
    using namespace std;
    class Solution {
    public:
    	vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    		vector<int>re;
    		if(nums.empty())
    			return re;
    		if(k==1)
    			return nums;
    		set<int,std::greater<int>>aa;
    		map<int,int>count;
    		for(int i=0;i<k;i++)
    		{
    			count[nums[i]]++;
    			aa.insert(nums[i]);
    		}
    		re.push_back(*aa.begin());
    		for(int i=1;i<=nums.size()-k;i++)
    		{
    			count[nums[i-1]]--;
    			if(count[nums[i-1]]==0)
    				aa.erase(aa.find(nums[i-1]));
    			count[nums[i+k-1]]++;
    			aa.insert(nums[i+k-1]);
    			re.push_back(*aa.begin());
    		}
    		return re;
    	}
    };
    
    int _tmain(int argc, _TCHAR* argv[])
    {
    	Solution sl;
    	int aa[6]={1,3,1,2,0,5};
    	vector<int>nums(aa,aa+6);
    	vector<int>re=sl.maxSlidingWindow(nums,3);
    
    	system("pause");
    	return 0;
    }

accepted