leetcode (11) - Container With Most Water-白红宇

leetcode (11) - Container With Most Water

阅读量：2182 次

发布时间：2019-05-02

本文共 1078 字，大约阅读时间需要 3 分钟。

题意：在一个坐标系中，给出若干点，每个点做x轴的垂直线，然后求任何两条线形成的容器中能盛下最多水的情况

分析：

1. 两层for循环， O(n^2)的算法， leetcode不给通过===> time limited exceed

2. O(n)的算法，只能定性的分析，还不能形式化证明，这个必须得证明，否则不能保证正确性。

定性说明：实际在二维坐标系中形成一个波动序列，从左开始与从右开始在分别到达极值之前，都有可能，之后的取值只有极值点才有可能出现变化。

证明应该是这样的：

i, j分别从头尾开始遍历，面积 area = min(height[j], height[i]) * (j-i)，

当height[i] < height[j]时，此时面积 area =

height[i] * (j-i);

由于height[i]是短板，不管跟谁组合，它能达到的最大面积取决于 j-i，而此时j-i的距离是最大的，因此，此面积即为以i为左边界的最大面积，然后++i, 放弃i短板和 j之前的板子的结合。

同理得j的变化。因为对于i, j，总有一个是短板，每次是短板的就发生变化，因此覆盖了所有情况。

int maxArea(int* height, int heightSize) {    int i=0, j=heightSize-1, height_tmp = 0, max_tmp =0,width_tmp = 1, max = 0;    int flag = 1;        while(i < j){            height_tmp = (height[i]>height[j])?height[j]:height[i];            width_tmp = j-i;            max_tmp = height_tmp * width_tmp;            if (max < max_tmp) {                max = max_tmp;            }                         if (height[i] < height[j])    // 因为长方形的宽度j-i已经是最大了，如果i不动，height[i]*任何( j减去一个值 ) 都会小于max, 所以放弃i                i++;            else                j--;        }        return max;}

转载地址：http://poxkb.baihongyu.com/

你可能感兴趣的文章