算法摘要

单调队列可以记录子数组的最值，次最值，等等

子数组的和可以转换为前缀和的差

子数组批量增删可以转化为差分数组的边界调整

二分法要考虑边界外的元素具备什么性质，具体看灵神视频教程。

⁠1. 数组类问题

技巧，

⁠1.1. 枚举右维护左

为什么？枚举右，在往右遍历的过程中，左边的信息必然已经遍历过，因此可以方便的对左边进行一些计算或记录，再结合左右关系求解问题。

典型例题（灵神题单）

1. 两数之和
2. 好数对的数目 1161 相当于两数之差等于 0
3. 与对应负数同时存在的最大正整数 1168 相当于两数之和等于 0
4. 买卖股票的最佳时机
5. ……

⁠1.2. 滑动窗口（双指针）

求和为target的子数组，我之前的写法是这样的：

int cur_sum = 0;
int gap = 0;
for (int i = 0, j = 0; i <= j && j <= nums.size();) {
	if (cur_sum < target) cur_sum += nums[j++];
	else if (cur_sum > target) cur_sum -= nums[i++];
	else {
		gap = max(gap, j - i);
		cur_sum -= nums[i++];
	}
}

这样写的问题在于判断条件多，且边界容易越界。

1. 遍历完之后，还要再进去一次，不然会漏更新答案。所以循环条件要设为 j <= nums.size()，但这又容易带来越界的问题。
2. 内部 i 可能超过 j.

滑窗的推荐写法应该如下，

int gap = 0, sum = 0;
for (int left = 0, right = 0; right < nums.size(); ++right) { // 外层扩张右边界
	sum += nums[right];
	while (sum > target) {
		sum -= nums[left++]; // 内层收缩左边界
	}
	if (sum == target) {
		gap = max(gap, right - left + 1);
	}
}

虽然看起来两个循环，但从元素遍历的角度来思考，每个元素至多遍历一次，时间复杂度仍然是 $O(n)$. 这样做的好处是，条件判断简单，边界清晰，不容易出错。