题解 | #c++ 滑动窗口#

class Solution {
public:
    /*不知道你们怎么解的，我一看这个就是经典滑动窗口，写完了但是耗时太多了，而且内存*/
    /* 消耗也多*/
    /*肯定有更好的方法，但是可以互相学习下，欢迎交流*/
    /*本题解函数*/
    vector<int> maxInWindows(const vector<int>& num, unsigned int size) {
        vector<int> result;//储存结果
        vector<int> windows;//滑动窗口
        int len = num.size();int left = -1;//左终止指针
        vector<int>::iterator it;
        if(len <= 0 || size <= 0){
            return result;
        }else{
            //枚举start指针
            for(int i = 0;i<len;i++){
 				//start进一个vector容器删除一个
                if(i!=0){
                    it = find(windows.begin(),windows.end(),num[i-1]);
                    if(it != windows.end()){
                        windows.erase(it,it+1);
                    }
                }
               //给滑动窗口插入值，每次只插入到start+size处
                while(left+1<i+size && left+1 < len){
                    windows.push_back(num[left+1]);
                    left++;
                }int maxelement = *max_element(windows.begin(),
                          windows.end());
              //将结果返回给result
                if(windows.size()==size){
                     result.push_back(maxelement);
                }
            }
        }
        return result;
    }
    /************下面是无关紧要的函数，想学习的可以看，都是与此题相关的经典的问题*************/
    /**************************************************************************/
    /*               1.最长无重复子序列长度 
     *               2.最长递增子序列
     *               3.最长无重复子序列
     */
    /*此方法用来返回最长无重复连续子序列的长度，不能返回具体的子序列*/
    /*动态规划*/
    int maxLenArray(vector<int> num){
        unordered_set<int> windows;
        int left = -1;int right = num.size();int ans = 0;
        for(int i = 0;i<right;i++){
            if(i!=0){
              windows.erase(num[i-1]);
            }while(left+1<right && !windows.count(num[left+1])){
                windows.insert(num[left+1]);left++;
            }
            ans = max(ans,(int)windows.size());
        }
        return ans;
    }
    /*此方法用来返回最长递增子序列（可以不连续) ，和最长值*/
    /*贪心*/
    vector<int> maxArray(vector<int> num){
        vector<int> result;vector<int> maxlen;
        if(num.size()<= 0){
            return result;
        }else{
            int len = num.size();result.push_back(num[0]);
            for(int i = 1;i<len;i++){
                if(num[i] >= result.back()){
                    result.emplace_back(num[i]);
                    maxlen.push_back(result.size());
                }else{
                    int post = lower_bound(result.begin(), 
                         result.end(),num[i]) - result.begin();
                    result[post] = num[i];
                    maxlen.push_back(post+1);
                }
            }//最大长度
            int index = *max_element(result.begin(), result.end());
            for(int i = len-1;i>=0;i--){
                if(maxlen[i] == index){
                    result[--index]= num[i];
                }
            }
            return result;
        }
    }
    /*此方法用来返回最长无重复子序列*/
    /*vector滑动窗口*/
    vector<int> maxNocopy(vector<int> arr){
        vector<int> result;vector<int> results;
        int left = -1;int maxlen = 0;int right = arr.size();
        vector<int>::iterator it;vector<int>::iterator it1;
        for(int i = 0;i<right;i++){
            if( i!= 0){
                it = find(result.begin(),result.end(),arr[i-1]);
                if(it != result.end()){
                    result.erase(it,it+1);
                }
            }
            while(left+1 < right ){
                it1 = find(result.begin(),result.end(),arr[left+1]);
                if(it1 == result.end()){
                    result.push_back(arr[left+1]);
                    left++;
                }else{
                    break;
                }
            }if(result.size() > maxlen){
                maxlen = result.size();
                results = vector<int> (maxlen,0);
                for(int i = 0;i<maxlen;i++){
                    results[i] = result[i];
                }
            }
        }
        return results;
    }
};