滑动窗口解题技巧

1.

2.LeetCode239.滑动窗口的最大值

本题我们维护一个双端队列，每次对要进来的元素进行判断，确保双端队列从队头到队尾是从大到小，队头存放当前窗口的最大值，为了确保是当前窗口最大值，就需要对队头进行判断。deq.front() == nums[i-k]就是检查是不是当前窗口。

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> res;
        deque<int> deq;
        int len = nums.size();

        for(int i = 0; i < len; i++){
            while (!deq.empty() && deq.back() < nums[i]) deq.pop_back();
            if (!deq.empty() && i >= k && deq.front() == nums[i-k]) deq.pop_front();
                 deq.push_back(nums[i]);

            if (i >= k-1) res.push_back(deq.front());
        }
        return res;
    }
};

2.LeetCode3.最长不含重复字符的字符串

C++(自己思路)

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        if (s.size() == 0) return 0;
        int Max = INT_MIN;
        int size = s.size();
        set<char> set;
        deque<char> deq;

        for (int i = 0; i < size; i++) {
           if (set.insert(s[i]).second) {
               deq.push_back(s[i]);
               if(i == size-1) Max = max((int)deq.size(), Max);
           }
           else{
               Max = max((int)deq.size(), Max); 
               while (!deq.empty()) {
                   set.erase(deq.front());
                   deq.pop_front();
                   if(set.insert(s[i]).second) {
                       deq.push_back(s[i]);
                       break;
                   }
               }
           }
        }
        return Max;


    }
};

C++(题解)

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        map<char,int> map;
        int size = s.size();
        int result=0;
        for (int left = 0, right = 0; right < size; right++) {
            if(map.find(s[right])!=map.end()) {
                left =max(map[s[right]]+1, left);
            }
            result = max(result, right - left + 1);
            map[s[right]] = right;
        }
        return result;

    }
};

C++终极简化版：

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int arr[256]={0};
        int size = s.size();
        int result=0;
        for (int left = 0, right = 0; right < size; right++) {
           char c=s[right];
           left=max(arr[c],left);
           result=max(result,right-left+1);
           arr[c]=right+1;
        }
        return result;
    }
};