引言
对于与数组子串相关的题我们以及见过很多了，根据遍历可以很轻松的将所有子串进行组合，但是我们针对不同类型的题目，可以通过一定的排除方式进行子串的挑选，这样可以让我们的程序更加高效。
题目：盛水最多的容器
(点进去查看题目）
解法：
- 最复杂简单的方法
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;
}
}
我们将数组起始点作为第一个指针，然后取最后一个数为最后一个指针。
那么我们为什么在比较两个指针的大小后就能判断让哪一个移动呢?
指针移动的原理
首先我们要知道我们为什么要移动指针。
- 现在假如我们的左指针所对应的数是比右指针大的，但是这时我们需要移动一次右指针，这是为什么呢？
- 假如我们移动较大的左指针那么，我们接下来是不可能找到比原来数组所组成的容积的。因为除了左指针的数，那么这个数组要么含有比右指针小，要么相等，要么比它大——比它小的话，那么因为横向长度变小，而且高度变小，所以一定是比原本数组所组成的小的。跟它相等的话，那么因为横向长度变小，所以也一定是比原本数组所组成的小的。比它大的话，因为高度不变，因为横向长度变小，所以也一定是比原本数组所组成的小的。所以综上情况，当左指针所对应的数是比右指针大的，这时我们需要移动一次右指针，而不是移动较大的指针
- 同理我们可以知道右指针所对应的数是比左指针大的，但是这时我们需要移动一次左指针。
- 那么当两个指针对应数相同时，我们移动哪一个指针呢？
实际上移动哪一个指针都是可以的，因为无论是移动哪一个相同的指针，另外一个指针都会将应该遍历的数组所遍历完的，直到遇到下一个两指针相同，或者当左指针与右指针相遇。所以可以知道当遇到相同的情况时，移动左右指针都是一样的。 - 这样我们的时间复杂度则大大降低，我们面向的不再是子串，而是两个指针。
总结
对于这种特殊条件的题目，我们可以通过充分理解题意，去除无关的数据，然后只判断有作用的数组，这样可以明显提高效率。
