两边夹的应用三

​对于两边夹的应用，这个主题之前写过两篇，今天这篇继续该系列。



题目可参见leetcode第11题，给定一组非负整数组成的数组，下标表示位置，数值表示位置的高度，求其中两个高度之间能储水的最大值，如题图所示。



先分析一下题目中储水量的求法，从图中可以看出，储水量可以理解为求蓝色部分的面积，也就可以转化为求矩形的面积，而矩形的宽为右下标减去左边下标的差值，而矩形的高是左右两边高度较小的一边，可得求解面积公式如下：



area = min(leftHeight, rightHeight) * (rightIndex - leftIndex)



知道了面积求法后，重点变成如何确定哪两个坐标间计算出的面积最大，如果用暴力求解的话，相当于每个坐标都要和其后续坐标求解一次，其时间复杂度为(n-1)*n/2，即O(n^2)。



现在我们同样以两边夹的方式考虑该问题，则计算方式可以按如下流程：

1、初始化左右指针为leftIndex为0， rightIndex为n-1（即数组的第一个和最后一个下标），最大面积area为0；

2、当leftIndex < rightIndex，做如下计算；

3、用面积公式求当前面积，并与当前最大面积相比较以决定是否更新最大面积，公式如下：

area = max(area, min(leftHeight, rightHeight) * (rightIndex - leftIndex))

4、更新左右指针，规则如下，如果leftHeight <= rightHeight，leftIndex++，否则rightIndex--，继续步骤2，直至条件不满足，执行5；

5、此时返回的area即为最大面积。



该计算过程最核心的步骤是第4步，如何更新左右指针。采用第4步所描述的方式，主要原因是，如果想让下一次的面积更大，只有保留当前较高的一边，让矮的一边移动以寻求更高的高度，才有可能得到更大的面积。如果移动较高的一边，则下一次的面积必然是减少的，不难理解，高度仍是较低的高度，而宽又减少了1。

​采用两边夹的方式需要计算n-1次，时间复杂度为O(n)。该计算过程用图来表示应该更好理解，所以画了如下示意图来简单表示该计算过程，图示仅演示了初始的几个步骤，剩余步骤方法相同，如下所示：



过程讲清楚了，就上代码吧：

public int maxArea(int[] height) {
    if (null == height || height.length < 2) {
        return 0;
    }
    int leftIndex = 0, rightIndex = height.length - 1;
    int area = 0;
  
    while (leftIndex < rightIndex) {
        area = Math.max(area, Math.min(height[leftIndex], height[rightIndex]) * (rightIndex - leftIndex));
        if (height[leftIndex] < height[rightIndex]) {
            leftIndex++;
        } else {
            rightIndex--;
        }
    }
    return area;
}



对于这个题目如果我们改个条件，要求计算最大值，并且返回相应的左右位置坐标，甚至可能不只一组坐标符合条件，要求返回最大值及所有的坐标组合，这就当对该题目的一个延伸，大家有兴趣可以实现一下​。



该系列其他文章：

两边夹的应用二

两边夹的应用