专题一 滑动窗口

1. 滑动窗口最大值

class Solution {
public:
    int q[100010];
    vector<int>res;
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int hh=0,tt=-1;
        for(int i=0;i<nums.size();i++)
        {
            if(hh<=tt&&i-k+1>q[hh])   hh++;
            while(hh<=tt&&nums[q[tt]]<=nums[i])tt--;
            q[++tt]=i;
            if(i-k+1>=0)
                res.push_back(nums[q[hh]]);
        }
        return res;
    }
};

2. 最小覆盖子串

维护字母出现次数

class Solution {
public:
    string minWindow(string s, string t) {
        unordered_map<char,int>hs,ht;
        for(int i=0;i<s.size();i++) ht[t[i]]++;
        int cnt=0;
        string res;
        for(int i=0,j=0;i<s.size();i++)
        {
            hs[s[i]]++;
            if (hs[s[i]]<=ht[s[i]])  cnt++;
            while(hs[s[j]]>ht[s[j]])
            {
                hs[s[j]]--;
                j++;
            }
            if (cnt==t.size())
            {
                if(res.empty()||i-j+1<res.size())
                {
                    res=s.substr(j,i-j+1);
                }
            } 
        }
        return res;
    }
};

862. 和至少为 K 的最短子数组

typedef long long ll;

class Solution {
public:
    int shortestSubarray(vector<int>& nums, int k) {
        int n=nums.size();
        vector<ll>s(n+1);
        for(int i=1;i<=nums.size();i++)  s[i]=s[i-1]+nums[i-1];
        deque<int>q;
        q.push_back(0);
        int res=INT_MAX;
        for(int i=1;i<=n;i++)
        {
            while(q.size()&&s[q.front()]+k<=s[i])
            {
                res=min(res,i-q.front());
                q.pop_front();
            }
            while(q.size()&&s[q.back()]>=s[i])q.pop_back();
            q.push_back(i);
        }
        if (res==INT_MAX) return -1;
        else return res;  
    }
};