讨论/《高级算法》 - 盛最多水的容器/
《高级算法》 - 盛最多水的容器
共 2 个回复

能盛水的最大值取决于h的最小值,因此根据h的大小去移动l r,感觉这个解释好牵强,看了官方的证明也感觉没说的很明白

int maxArea(int* height, int heightSize){
    int l = 0, r = heightSize - 1, res = 0, h = 0;
    while (l < r) {
        h = fmin(height[l], height[r]);
        res = fmax(res, h * (r - l));
        if (height[l] <= height[r]) {
            l++;
        } else {
            r--;
        }
    }
    return res;
}

暴力肯定超时

int maxArea(int* height, int heightSize){
    int res = 0, h = 0;
    for (int i = 0; i < heightSize; i++) {
        for (int j = 0; j < heightSize; j++) {
            h = fmin(height[i], height[j]);
            res = fmax(res, h * (j - i));
        }
    }
    return res;
}