双指针算法实战：盛最多水的容器与有效三角形个数

前言

本文介绍两个题目，盛最多水的容器和有效三角形的个数，对应的 Leetcode 的题目链接为：

11. 盛最多水的容器 - 力扣（LeetCode）

611. 有效三角形的个数 - 力扣（LeetCode）

介绍这两个题目，会从两角度进行介绍，暴力解法以及算法，整个题目的讲解分为三个部分，题目解析，算法原理，算法编写三个部分进行讲解。

盛最多水的容器

题目解析

题目要求找到最大的值，值的求法为下标相减 * 两数中小的那个数。我们可以直接暴力，即将所有的值都给求出来，自然是两个循环就可以解决了，伪代码为：

for(...) {
    //确定左边的边长
    for(...) {
        //确定右边的边长
    }
}

虽然说最后求值部分是一个等差数列的求和方式，但是不影响，最终的时间复杂度依旧是 O(N^2)。

对于为什么求值是 * 两数中较小的那个数，木桶效应相信大家都是听说过的：即一个木桶盛水的容量不是取决于最长的木板，而是最短的那个木板，所以求值的时候是最小的那个值。

算法原理

在算法原理部分，我们已经在上文了解了暴力解法，所以不再赘述暴力解法，这里是找两个数，保证下标相减 * 最小的那个数是最大值，那么找两个数，我们不妨使用双指针来解决。

容量大小 = 两数中的较小值 * 下标之差

我们不妨规定左指针从 0 开始，右指针从 size - 1 开始，如果我们从同向的方向进行判断，那么就会存在两变量，下标之差可能增大可能减少，较小值不确定，就会有 4 种情况，是比较难控制的。如果是我们定向的让右指针从右边开始，即数组的最末端，随着右指针往左或者是左指针往右，都是下标之差减少的过程，那么我们为了找最大值，需要保证的就是两个数之间的规则了。

谁小谁就移动，并且我们需要记录移动之前的容量大小，记录之后，需要比较移动之后的容量大小。我们取最大的即可。

算法编写

class Solution {
public:
    int maxArea(vector<int>& height) {
        int left = 0, right = height.size() - 1;
        int ret = 0, ans = 0;
        while(right > left) {
            ret = min(height[left], height[right]) * (right - left);
            ans = max(ret, ans);
            if(height[left] > height[right]) right--;
             left++;
        }
         ans;
    }
};