对撞型,灌水类
双指针算法普遍分为三种
对撞类
two sum 类,partition 类
窗口类
并行型
掌握 3-way partition 和 k-way partition.
对撞型指针的本质是,不需要扫描多余的状态。在两边指针的判断之后,可以直接跳过其中一个指针与所有另外一面 index 组成的 pair.
这道题如果暴力搜索的话,需要考虑的 pair 个数显然是 O(n^2). 但是用对撞型指针,可以有效跳过/剪枝不合理的 pair 组合。
排序之后的数组具有了单调性,两根指针的移动就代表了“增加”和“减少”。这种单调性保证了一条重要性质:
如果 nums[i] + nums[j] > target,那么 nums[i ~ j-1] + nums[j] > target.
因此 i,j 指向的不仅仅是元素,也代表了利用单调性,i,j 之间所有的 pair.
总的思路对了,但是一开始的做法掉到了坑里,就是用 i = 1 to n 做最外循环,j 和 k 都在 i 后面。
这种思路的问题是,想 num[i] + num[j] > num[k]的话,如果当前条件不满足,j++ 和 k-- 都可以是对的。就违反了双指针不同程度上利用的单调性,一次只把一个指针往一个方向推,而且不回头。
所以顺着这个问题想,如果我们最外围遍历的是 k,而 i, j 都处于 k 的左面,那么每次就只有一个正确方向,挪动一个指针可以保证正确性了,即让 num[i] + num[j] 变大,或者变小。
这种“灌水”类问题和双指针脱不开关系,都要根据木桶原理维护边界;在矩阵中是外围的一圈高度,在数组中就是左右两边的高度。
因为最低木板的高度决定水位,高位的木板有着另一种单调性,即高位木板向里移动的所有位置,形成的 container 水量都小于原来位置。
Trapping Rain Water
木桶原理的算法版,最两边的板子形成一个木桶,由两块板子最低的那块决定水位。每次都从两边最低的方向向里扫描。
因为 i,j 当前高度未必是当前左右两边最高高度,每次更新的时候要注意维护下。
Last updated