Container With Most Water

[barretlee]

本题难度：★★

给定 N 个非负整数 a₁, a₂, ..., a_n, 每个数对应坐标上的一个点 (i, a_i)，在坐标轴上将所有的 (i ,0) 和 (i, a_i) 使用直线链接起来。

任何两条 相邻的 线 （包含 Y 轴） ，这两条线与 X 轴构成一个容器，找出容量最大的容器对应的线。

注意：不能够倾斜容器，并且 n 不小于 2。

[barretlee]

刚开始题设是相邻的线，并且可以包含 Y 轴，写了一个答案：

function resolve(arr) {
  var max = 0;
  var maxIndex = 0;
  for (var i = 0, len = arr.length; i < len; i++) {
    var tmp = Math.min(arr[i], arr[i - 1] || Number.POSITIVE_INFINITY);
    if (tmp > max) {
      tmp = max;
      maxIndex = [i, i - 1];
    }
  }
  return maxIndex;
}

resolve([3, 4, 3, 8, 2, 7, 9]); // -> [6, 5]

[pengkobe]

haha~ Time Limit Exceeded

def Container_With_Most_Water(arr):
    maxArea = 0;
    arrLen = len(arr);
    for i in range(arrLen):
        for j in range(i+1,arrLen):
            height = arr[i] if arr[i] < arr[j] else  arr[j];
            if maxArea < height * (j - i):
                maxArea =  height * (j - i);

    return maxArea
print(Container_With_Most_Water([3, 4, 3, 8, 2, 7, 9]));

正解

def Container_With_Most_Water(arr):
    maxArea = 0;
    arrLen = len(arr);
    i,j = 0,arrLen -1;
    while (i < j):
        height = arr[i] if arr[i] < arr[j] else  arr[j];
        maxArea = max(maxArea, height*(j-i));
        if arr[i] < arr[j]:
            i +=1;
        else:
            j -=1;
    return maxArea;


print(Container_With_Most_Water([3, 4, 3, 8, 2, 7, 9]));

[YabZhang]

def resolve_v1(alist):
    """
    一个非负整数序列，把(i, 0)和(i, ai)连线；
    求相临边围成的最大面积，包含y轴；
    """
    buckets = [alist[0]] + list(alist)
    max_index, max_result = 0, 0
    for i in range(len(alist)):
        if min(buckets[i] + buckets[i + 1]) > max_result:
            max_index, max_result = i, min(buckets[i], buckets[i + 1])
    return buckets[max_index], buckets[max_index + 1]


def resolve_v2(alist):
    """
    去除边界相临的限制条件，且不包含y轴；
    法１: 暴力查询法,O(n^2)
    """
    max_index = [0, 0]
    max_result = 0
    for i in range(len(alist) - 1):
        for j in range(i + 1, len(alist)):
            area = (j - i) * min(alist[i], alist[j])
            if area > max_result:
                max_result = area
                max_index = [i, j]
    return max_result, max_index


def resolve_v2(alist):
    """优化算法，O(n)"""           
    head, tail = 0, len(alist) - 1
    max_result = 0
    max_index = [head, tail]
    while head < tail:
        height = min(alist[head], alist[tail])
        t_area = height * (tail - head)
        if t_area > max_result:
            max_result = t_area
            max_index = [head, tail]
        if alist[head] > alist[tail]:
            tail -= 1
        else:
            head += 1
    return max_result, max_index