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. 最小覆蓋子串
維護字母出現(xiàn)次數(shù)
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 的最短子數(shù)組
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;
}
};
