python - 极客的极客 两座建筑之间的最大水量

Question

我正在尝试解决 GeeksClasses 中的一个问题，但我的提交有问题。我的代码有效，但他们说您的程序花费的时间比预期的要多。时间限制超出预期的时间限制 < 3.448 秒提示：请优化您的代码并再次提交。

https://practice.geeksforgeeks.org/problems/maximum-water-between-two-buildings/1/?track=SPCF-Searching&batchId=154

问题陈述：

给定一个大小为 N 的整数数组高度，表示 N 个建筑物的高度，任务是删除 N-2 个建筑物，以使剩余两座建筑物之间的水量最大。请注意，两座建筑物之间的总水量是它们之间的差距（拆除的建筑物数量）乘以较小建筑物的高度。

输入格式：

输入的第一行包含 T 表示测试用例的数量。T 测试用例如下。每个测试用例包含两行输入。第一行包含 N 表示数组中元素的数量。第二行包含数组的元素。

输出格式：

对于每个测试用例，在新行中打印移除 n-2 座建筑物后任意两座建筑物之间可以储存的最大水量。

这是我的代码：

def maxWater(height, n): 
    maximum = 0;  
  
    # Check all possible pairs of buildings  
    for i in range(n - 1) : 
        for j in range(i + 1, n) : 
            current = min(height[i],  
                          height[j]) * (j - i - 1);  
  
            # Maximum so far  
            maximum = max(maximum, current);  
              
    return maximum;  

标签： pythonpython-3.x

Answer 1

您的问题是您编写了一个二次时间解决方案 ( O(n^2))，而该问题的最佳解决方案是线性 ( O(n))。

提示：两座建筑物之间的蓄水量取决于两座建筑物中较短的一座的高度。