1 滑动窗口
priority_queue经常用
0480 滑动窗口中位数
1 题目
https://leetcode-cn.com/problems/sliding-window-median/
2 解题思路
- 1 使用一个multiset维护当前窗口，
- 1.1 不使用priority_queue的原因，无法删除元素
- 1.2 不使用map/set的原因，不能含有重复元素
- 2 对于窗口，维护一个中位数指针，注意到中位数指针在每一次窗口移动只会发生几种情况
- 2.1 向左，向右，不动
- 2.2 分类讨论清除即可
class Solution {
public:
vector<double> medianSlidingWindow(vector<int>& nums, int k) {
long long n = nums.size();
std::multiset<long long, std::less<long long>> mySet(nums.begin(), nums.begin() + k);
vector<double> res;
multiset<long long>::iterator mid = mySet.begin();
std::advance(mid, (k-1)/2);
for(long long i = k; i <= n; ++i) {
res.emplace_back((*mid + *next(mid, 1 - k%2))*1.0L/2);
if(i == n) break;
mySet.insert(nums[i]);
if (nums[i] > *mid && nums[i - k] < *mid) {
mid++;
mySet.erase(mySet.lower_bound(nums[i-k]));
continue;
// std::advance(mid, 1);
}
if (nums[i] < *mid && nums[i - k] > *mid) {
mid--;
mySet.erase(mySet.lower_bound(nums[i-k]));
continue;
// std::advance(mid, -1);
}
// 7 3 7 7 4, k = 4
// 7 8 7 7 4, k = 4
if(nums[i-k] == *mid) {
if(nums[i] >= *mid) ++mid;
else {
if(*prev(mid) != *mid) {
--mid;
}
}
mySet.erase(mySet.lower_bound(nums[i-k]));
continue;
}
if(nums[i] == *mid) {// 相当于一个比mid大的数字插入到了mid的前面
if(nums[i-k] <= *mid) ++mid;
mySet.erase(mySet.lower_bound(nums[i-k]));
continue;
}
}
return res;
}
};
0992 k个不同元素的子数组个数
1 题目
https://leetcode-cn.com/problems/subarrays-with-k-different-integers/submissions/
2 解题思路
- 1 正常思路：
- 1.1 首先窗口是必须的，即为[st, ed]，那么保证这个窗口时刻含有k个不同变量，然后求出来每个以ed为结尾的子数组的个数求和即可
- 1.2 那么以ed为结尾的窗口[st, ed]的子数组个数求法，假设k=2，窗口为1,2，1,2,那么以ed为结尾，st就向前移动，直到窗口内的不同元素个数减少到了k-1，此时st移动到第二个2的位置，一共移动了3次，也就是说以ed为结尾的含有k个不同变量的子数组个数为3。
- 1.3 其中的复杂之地在于：如何判断窗口内不同元素的个数，我们采用经典的空间换时间的方法(因为所有元素的值不会大于数组本身长度),用freq[val]记录val出现的次数， 倘若长度不限呢？那就需要使用unordered_map来记录当前窗口所有元素的出现次数，然后每移动一次st需要遍历一遍这个map来判断当前窗口内不同元素的个数，那么整体复杂度为： o(n * k * k)
- 2 官方题解：
- 2.1 不同元素为k的子数组的个数为： 不同元素最多为k的子数组个数 - 不同元素最多为k-1的子数组个数，那么问题转为求不同元素最多为k的一个数组它子数组的个数
- 2.2 求法： 还是滑动窗口的思想，始终保持窗口中最多元素的个数不超过k（方式为每次移动ed，直到第一次超过k，然后移动st直到小于k），然后对于每个ed，ed - st就是以ed为窗口结尾对应的不同元素不超过k的子数组的个数，举个例子：(官方例子)：
用具体的例子理解：最多包含 3 种不同整数的子区间 [1, 3, 2, 3] （双指针算法是在左边界固定的前提下，让右边界走到最右边），当前可以确定 1 开始的满足最多包含 3 种不同整数的子区间有 [1]、[1, 3]、[1, 3, 2]、[1, 3, 2, 3]。
class Solution {
public:
int subarraysWithKDistinct(vector<int>& nums, int k) {
return maxSubArrayNumForKDiff(nums, k) - maxSubArrayNumForKDiff(nums, k - 1);
}
int maxSubArrayNumForKDiff(vector<int>& nums, int k) {
vector<int> freq(nums.size() + 1);
long long res = 0;
int st = 0;
int ed = 0;
int curCnt = 0;
while(ed < nums.size()) {
// 求每个ed对应得到的最多k个不同元素的子数组个数
if(freq[nums[ed]] == 0) {
curCnt ++;
}
freq[nums[ed]]++;
++ed;
// 减小窗口到窗口内元素种类第一次为k-1个
while(curCnt > k) {
freq[nums[st]]--;
if(freq[nums[st]] == 0) {
curCnt--;
}
++st;
}
res += ed - st;
}
return res;
}
};
0904 完全水果个数
1 题目
https://leetcode-cn.com/problems/fruit-into-baskets/
2 解题思路
- 1 正常思路：(于0904https://leetcode-cn.com/problems/fruit-into-baskets/实现)
- 1.1 首先窗口是必须的，即为[st, ed]，那么保证这个窗口时刻含有k个不同变量，然后求出来每个以ed为结尾的子数组的个数求和即可
- 1.2 那么以ed为结尾的窗口[st, ed]的子数组个数求法，假设k=2，窗口为1,2，1,2,那么以ed为结尾，st就向前移动，直到窗口内的不同元素个数减少到了k-1，此时st移动到第二个2的位置，一共移动了3次，也就是说以ed为结尾的含有k个不同变量的子数组个数为3。
- 1.3 其中的复杂之地在于：如何判断窗口内不同元素的个数，我们采用经典的空间换时间的方法(因为所有元素的值不会大于数组本身长度),用freq[val]记录val出现的次数， 倘若长度不限呢？那就需要使用unordered_map来记录当前窗口所有元素的出现次数，然后每移动一次st需要遍历一遍这个map来判断当前窗口内不同元素的个数，那么整体复杂度为： o(n * k * (log k)) = o(n)
- 2 官方题解：
- 2.1 不同元素为k的子数组的个数为： 不同元素最多为k的子数组个数 - 不同元素最多为k-1的子数组个数，那么问题转为求不同元素最多为k的一个数组它子数组的个数
- 2.2 求法： 还是滑动窗口的思想，始终保持窗口中最多元素的个数不超过k（方式为每次移动ed，直到第一次超过k，然后移动st直到小于k），然后对于每个ed，ed - st就是以ed为窗口结尾对应的不同元素不超过k的子数组的个数，举个例子：(官方例子)：
用具体的例子理解：最多包含 3 种不同整数的子区间 [1, 3, 2, 3] （双指针算法是在左边界固定的前提下，让右边界走到最右边），当前可以确定 1 开始的满足最多包含 3 种不同整数的子区间有 [1]、[1, 3]、[1, 3, 2]、[1, 3, 2, 3]。
class Solution {
public:
int totalFruit(vector<int>& fruits) {
if(fruits.size() <= 1) {
return 1;
}
// 不同元素最多为2的数组长度
int res = 0;
int st = 0;
int ed = 0;
int curCnt = 0;
map<int, int> freq;
bool stNotMov = true;
while(ed < fruits.size()) {
while(freq.size() <= 2 && ed < fruits.size()) {
if(freq.find(fruits[ed]) == freq.end()) {
curCnt++;
}
freq[fruits[ed]]++;
ed++;
}
if(!stNotMov && ed != fruits.size()) {
res = std::max(res, ed - st - 1);
} else {
if(freq.size() == 3) {
res = std::max(res, ed - st - 1);
} else {
res = std::max(res, ed - st);
}
}
while(freq.size() > 2) {
freq[fruits[st]]--;
if(freq[fruits[st]] == 0) {
freq.erase(freq.find(fruits[st]));
}
++st;
stNotMov = false;
}
}
return res;
}
};
0995 执行次数最小: 每次翻转k个让数组全为1
1 题目
https://leetcode-cn.com/problems/minimum-number-of-k-consecutive-bit-flips/
2 解题思路
- 1 正常思路：窗口始终保持k个，去模拟翻转过程，由于需要在窗口内找到翻转后第一个为0的数字，这个复杂度为O（k），所以总复杂度为： O(n*k)
- 2 官方题解：使用差分数组diff,diff[i]表示nums[i]比nums[i-1]多了多少次翻转，那么当前总的翻转次数就为： sum(diff[i])，对于nums[i]而言， sum(diff[i])%2为0则表示nums[i]需要翻转。
class Solution {
public:
int minKBitFlips(vector<int>& nums, int k) {
vector<long long> preSum = {0};
for(long long num : nums) {
preSum.emplace_back(preSum.back() + num);
}
long long st = 0;
long long ed = st + k - 1;
long long n = nums.size();
long long res = 0;
vector<long long> diff(n+1);
long long flipCnt = 0;
// while(st < n - k + 1) {
// 模拟思路会超时
// if(nums[st] == 1) {
// ++st;
// continue;
// }
// int newSt = flipKBit(nums, k, st, preSum);
// if(newSt == -1) {
// st = st + k;
// } else {
// st = newSt;
// res += 1;
// }
// }
// if(find(nums.end() - k, nums.end(), 0) == (nums.end())) {
// return res;
// }
while(st < n) {
// 采用查分数组记录每个元素应该翻转的次数
// 这启发我们用差分数组的思想来计算当前数字需要翻转的次数。我们可以维护一个差分数组 \textit{diff}diff，其中 \textit{diff}[i]diff[i] 表示两个相邻元素
// \textit{nums}[i-1]nums[i−1] 和 \textit{nums}[i]nums[i] 的翻转次数的差，对于区间 [l,r][l,r]，将其元素全部加 11，只会影响到 ll 和 r+1r+1 处的差分值，
// 故 \textit{diff}[l]diff[l] 增加 11，\textit{diff}[r+1]diff[r+1] 减少 11。
flipCnt += diff[st];
if((flipCnt + nums[st]) % 2 == 0) {
if(st + k > n) {
return -1;
}
diff[st] ++;
diff[st + k] --;
res++;
flipCnt ++;
}
++st;
}
return res;
}
// 翻转kbit，返回第一个翻转窗口中反转后值不等于1的下标，否则返回-1
int flipKBit(vector<int>& nums, int k, int st, vector<int>& preSum) {
int firstNot1 = INT_MAX;
// 需要O(k)时间的复杂度
bool needFlip = find(nums.begin() + st, nums.begin() + st + k, 0) != (nums.begin() + st + k);
// 使用前缀和优化，由于实地翻转了数组，于是会改变对应的前缀和，所以此方法行不通
// bool needFlip = ((preSum[st + k] - preSum[st]) != k);
// for(int i = st; i < k; ++i) {
// if(nums[st + i] != 1) {
// needFlip = true;
// }
// }
if(needFlip) {
for(int i = 0; i < k; ++i) {
nums[st + i] = abs(nums[st + i] - 1);
if(nums[st + i] != 1) {
firstNot1 = min(firstNot1, st + i);
}
}
return firstNot1 > nums.size() ? st + k : firstNot1 ;
}
return -1;
}
};
1696 最大结果
1 题目
https://leetcode-cn.com/problems/jump-game-vi/submissions/
2 解题思路
- 1 采用动态规划：dp[i]表示跳到i处的最大收益,如下：搜索i的前k个下标即可
// o(n * k)解法
dp[0] = 0;
dp[1] = nums[0];
for(int i = 1; i < nums.size() + 1; ++i) {
for(int m = 1; m < k + 1 && i - m > 0; ++m) {
dp[i] = max(dp[i], dp[i-m] + nums[i-1]);
}
}
- 2 优化上述搜索前k个下标的方案，我们采用优先队列来维护前k个中最大的上一跳：
- 将上述O(n*k)变为O(n*logk)，原因是maxHeap的push操作是logN的复杂度
class Solution {
public:
struct number {
long long idx = 0;
long long val = 0;
number(long long idx, long long val): idx(idx), val(val) {};
// sort descending
bool operator<(const number& b) const {return this->val < b.val;}
};
int maxResult(vector<int>& nums, int k) {
vector<long long> dp(nums.size() + 1, INT_MIN);
// o(n * k)解法
dp[0] = 0;
dp[1] = nums[0];
// for(int i = 1; i < nums.size() + 1; ++i) {
// for(int m = 1; m < k + 1 && i - m > 0; ++m) {
// dp[i] = max(dp[i], dp[i-m] + nums[i-1]);
// }
// }
std::priority_queue<number, std::vector<number>, std::less<number>> maxHeap;
maxHeap.push({1, nums[0]});
// 使用堆优化：
for(int i = 2; i < nums.size() + 1; ++i) {
while(maxHeap.top().idx < i - k) {
maxHeap.pop();
}
dp[i] = maxHeap.top().val + nums[i - 1];
maxHeap.push({i, dp[i]});
// for(int m = 1; m < k + 1 && i - m > 0; ++m) {
// dp[i] = max(dp[i], dp[i-m] + nums[i-1]);
// }
}
return dp[nums.size()];
}
};
总结
滑动窗口的最大值：可以使用maxHeap来维护，复杂度logk