思想

今天下了一整天的雨，多么适合分析一下「解雨水」这道题及其方法——双指针。双指针的思路是，采用两个指针分别记录两个不同的位置，从而完成题目。常见的情景有：

  1. 快慢指针。在链表中讨论；
  2. 相向滑动指针。如解雨水和最大接水容器；
  3. 同向滑动窗口。在滑动窗口专题讨论。

题目

11. Container With Most Water

这道题给了我们一堆间隔为 1、高度不同的柱子，要求找出哪两个柱子之间能盛放最多的水。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int maxArea(vector<int>& height) {
        int ans = 0;
        int left = 0, right = height.size() - 1;

        while (left < right) {
            int area = min(height[left], height[right]) * (right - left);
            ans = max(ans, area);

            if (height[left] < height[right]) {
                left++;
            }
            else {
                right--;
            }
        }

        return ans;
    }
};

这道题可以反映短板效应。一个容器的容量的计算公式为：

$$
Volume = min(Hleft, Hright) * Width
$$

因此一开始让宽度最大，确保 $Width$ 变量已经做到了极限。在这个情况下，根据上述公式，得到一个结果。

接下来该移动边界了，哪边要缩小？根据公式分析，如果高板一侧缩小，那么，新容器的宽度减小、且高度肯定比现在低。说明什么？

如果挪动高板，肯定不会得到更好的解了。

那么，挪动短板一侧的界限，或许能得到更高的板，使得原来容器的高板成为短板，从而新容器的容量更大。

有人说，那，我就一直挪动高板一侧的边界，会不会万一有转机？

你指的是什么样的转机？如果得到更短的板，肯定不是转机。但就算得到更高的板，容器的容量还是被短板限制。所以必须挪动短板！补短板很重要。

15. 3Sum

这题要求我们找出数组中所有 unique 的三个数，s.t. 这三个数的和为 0。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        vector<vector<int>> ans;

        for (int i = 0; i < n; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            
            int left = i + 1, right = n - 1;

            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];

                if (sum == 0) {
                    ans.push_back({nums[i], nums[left], nums[right]});

                    while (left < right && nums[left] == nums[left + 1]) {
                        left++;
                    }
                    while (left < right && nums[right] == nums[right - 1]) {
                        right--;
                    }
                    left++, right--;
                }
                else if (sum > 0) {
                    right--;
                }
                else {
                    left++;
                }
            }
        }

        return ans;
    }
};

这题是怎么用双指针的呢？其实这道题是两数之和的拓展：先固定一个数，剩下的两个数作为两数之和来考虑。而在有序数组中，可以用两个指针来分别指向最大数和最小数。

复盘上面算法的逻辑。首先，考虑每个数作为定点的情况，为了防止重复考虑，left 和 right 只考虑这个点后续的数。

这道题的难点在于重复的处理。为了方便处理，先排序。对于定点，如果它前序和它相等，则不考虑当前点，因为之前已经考虑过相同的数。

而当找到一组解后呢？先加到返回向量中，再收缩边界：对于左侧边界，如果下一位和这一位相同，则收缩边界，右侧同理。最后，要再收缩一次。因为上面 while 退出时，边界指向的仍然是当前值，已经被考虑过了。

42. Trapping Rain Water

滴滴答、雨在下、今天都没停过呀。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    int trap(vector<int>& height) {
        int left = 0, right = height.size() - 1;
        int left_max = 0, right_max = 0;
        int ans = 0;
        
        while (left < right) {
            left_max = max(left_max, height[left]);
            right_max = max(right_max, height[right]);
            
            int h = min(left_max, right_max);

            if (left_max < right_max) {
                ans += (h - height[left]);
                left++;
            }
            else {
                ans += (h - height[right]);
                right--;
            }
        }

        return ans;
    }
};

这道题的思路和最大容器的类似。核心的思路是：一个坑，或者一个位置最多能接多少水呢？取决于 $min(左边最高, 右边最高) - 当前高度$。这个道理是显然的。

那么该如何考虑这件事呢？我们需要为每个元素遍历左边最高和右边最高，逐个考虑吗？复杂度太高了。

按这个思路来，还是从最边界的情况开始。现在，有了 left_max 和 right_max，问你，该收缩哪里的边界？还是矮的那一侧。为什么？

分析一下，如果左边更矮，那么对于最左边的那根柱子，站在它的角度思考，能得到什么呢？

柱子想：我左边最高也就是 left_max 了（因为已经考虑过它左边的所有位置），右边还未考虑的那些柱子可能比 right_max 高，也可能更低，但不管怎样，最大值就由 left_max 定了。

所以，最左侧的位置可以下结论了，left++。而对右侧的柱子却不能下结论。右侧的柱子想：现在左边的最大高度比右边矮，但，左边还有一些柱子（left 和 right 之间的）没考虑，它们可能比现在的左边最大值大，还有上升空间，让子弹再飞一会。

283. Move Zeros

这道题让我们把 0 挪到数组的最后。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int slow = 0;

        for (int fast = 0; fast < nums.size(); fast++) {
            if (nums[fast]) {
                swap(nums[fast], nums[slow]);
                slow++;
            }
        }
    }
};

思想是这样的，一个慢指针始终指向最靠前的 0，一个快指针往后遍历。当快指针发现一个非 0 元素时，交换，把非 0 元素往数组的前方放置。

另一种思考方式是，这道题让我们把非 0 数挪到数组的前面来。这样的话，每当发现一个非 0 元素后，就和数组最靠前的 0 进行交换。结束的时候，所有非 0 元素肯定都聚集在数组靠前位置。

我觉得很巧妙。