引言

对于与数组子串相关的题我们以及见过很多了，根据遍历可以很轻松的将所有子串进行组合，但是我们针对不同类型的题目，可以通过一定的排除方式进行子串的挑选，这样可以让我们的程序更加高效。

题目：盛水最多的容器

(点进去查看题目）

解法：

• 最复杂简单的方法

class Solution {
    public int maxArea(int[] height) {
         int mincompare=0;
         int maxContent=0;
         int nowContent=0;
        for (int i = 0; i < height.length-1; i++) {
            for (int j = i+1; j <height.length; j++) {
                mincompare=Math.min(height[i],height[j]);
                nowContent=mincompare*(j-i);
                if(nowContent>maxContent)
                {
                    maxContent=nowContent;
                }
            }
        }
        return maxContent;
    }
}

这样我们没有使用限定方式，直接将每一个子串的容积记录下来，然后再进行连续比较，但是这样的消耗的时间是O（n2），是不符合我们题目所容忍的时间的。所以我们要运用一个可以降低时间消耗的方式。

• 双指针连续判断
  我们先看代码。

public class Solution {
    public int maxArea(int[] height) {
        int l = 0, r = height.length - 1;
        int Maxarea = 0;
        while (l < r) {
            int Nowarea = Math.min(height[l], height[r]) * (r - l);
           Maxarea = Math.max(Maxarea, Nowarea);
            if (height[l] <= height[r]) {
                ++l;
            }
            else if(height[l] > height[r]){
                --r;
            }
        }
        return Maxarea;
    }
}

我们将数组起始点作为第一个指针，然后取最后一个数为最后一个指针。
那么我们为什么在比较两个指针的大小后就能判断让哪一个移动呢?

指针移动的原理

首先我们要知道我们为什么要移动指针。

• 现在假如我们的左指针所对应的数是比右指针大的，但是这时我们需要移动一次右指针，这是为什么呢？
• 假如我们移动较大的左指针那么，我们接下来是不可能找到比原来数组所组成的容积的。因为除了左指针的数，那么这个数组要么含有比右指针小，要么相等，要么比它大——比它小的话，那么因为横向长度变小，而且高度变小，所以一定是比原本数组所组成的小的。跟它相等的话，那么因为横向长度变小，所以也一定是比原本数组所组成的小的。比它大的话，因为高度不变，因为横向长度变小，所以也一定是比原本数组所组成的小的。所以综上情况，当左指针所对应的数是比右指针大的，这时我们需要移动一次右指针，而不是移动较大的指针
• 同理我们可以知道右指针所对应的数是比左指针大的，但是这时我们需要移动一次左指针。
• 那么当两个指针对应数相同时，我们移动哪一个指针呢？
  实际上移动哪一个指针都是可以的，因为无论是移动哪一个相同的指针，另外一个指针都会将应该遍历的数组所遍历完的，直到遇到下一个两指针相同，或者当左指针与右指针相遇。所以可以知道当遇到相同的情况时，移动左右指针都是一样的。
• 这样我们的时间复杂度则大大降低，我们面向的不再是子串，而是两个指针。

总结

对于这种特殊条件的题目，我们可以通过充分理解题意，去除无关的数据，然后只判断有作用的数组，这样可以明显提高效率。