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;
}
};