Sliding-Window Hard

Abstract: leetcode Sliding-Window

76. Minimum Window Substring

解法一【超时】

对于每一个start，复制一份HashTable，当表全小于0时更新最小长度，但由于本质还是暴力匹配，就超时了

解法二：滑动窗口

先找右边界，再缩小左边界

class Solution {
public:
    string minWindow(string s, string t) {
        unordered_map<char, int> tmap, cmap;
        for(const char& c : t) ++tmap[c];

        int l = 0, r = 0, min_len = INT32_MAX, res = -1, wnd_len = 0;
        while(r < s.length()) {
            if(tmap.find(s[r]) != tmap.end())
                ++cmap[s[r]];
            while(l <= r && check(cmap, tmap)) {
                if(r - l + 1 < min_len) {
                    min_len = r - l + 1;
                    res = l;
                }
                --cmap[s[l]];
                ++l;
            }
            ++r;
        }
        return res == -1 ? "" :s.substr(res, min_len);
    }

    bool check(unordered_map<char, int>& cmap, unordered_map<char, int>& tmap) {
        for(auto& k : tmap) {
            if(cmap[k.first] < k.second)
                return false;
        }
        return true;
    }
};

回溯优化

重复check两个map很费时间

class Solution {
public:
    string minWindow(string s, string t) {
        unordered_map<char, int> tmap;
        for(const char& c : t) ++tmap[c];

        int l = 0, r = 0, min_len = INT32_MAX, res = -1, wnd_len = 0;
        while(r < s.length()) {
            if(--tmap[s[r]] >= 0) ++wnd_len;
            while (wnd_len == t.length()) {
                if(r - l + 1 < min_len) {
                    min_len = r - l + 1;
                    res = l;
                }
                if(++tmap[s[l]] > 0) --wnd_len;
                ++l;
            }
            ++r;
        }
        return res == -1 ? "" : s.substr(res, min_len);
    }
};

239. Sliding Window Maximum

解法一：单调队列模板题

维护一个单调队列，详细请看Design篇

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        if(nums.empty() || k > nums.size() || k <= 0) return {};
        vector<int> res;
        deque<int> q;
        int len = nums.size();
        for(int i = 0; i < len; i++) {
            // window划过原先的最大值，弹出最大值
            if(!q.empty() && q.front() == i - k) q.pop_front();
            // 尾部如果小于nums[i]，直接弹出，因为他们在窗口范围内不可能是最大值
            while(!q.empty() && nums[i] > nums[q.back()]) q.pop_back();
            q.push_back(i);
            // 前k个，窗口大小不足k，跳过
            if(i < k - 1) continue;
            // 更新当前位置slidingwindow的最大值
            res.push_back(nums[q.front()]);
        }
        return res;
    }
};