接水问题-短板效应

问题描述

在一个二维坐标系中竖立了很多根柱子（从0~n），这些柱子各有一个高度，每两个柱子能形成一个容器，底是距离，高是短的那根柱子，求最大接水量。

解决思路

双指针法：头尾指针各一，每次移动矮的那个，直到两者重合。

int maxValue(int[] height){
    int i = 0;
    int j = height.length - 1;
    int ans = 0;
    while(i < j){
        ans = Integer.max(ans, (j - i) * Integer.min(height[i], height[j]));
        if(height[i] > height[j]){
            --j;
        } else {
            i++;
        }
    }
    return ans;
}

原因：如果动高的那根柱子，那么由于容器变短了，而高度变矮或者不变，接的水一定变少了，所以每次移动矮的那根柱子才有效。