如果我们移除它们之间的所有条,那么在2个条之间可以收集的最大水量是多少？

Question

给定一个整数数组,表示站在地面上的相邻垂直条的高度.

每个条的宽度为1.现在你必须选择两个条并移除它们之间的条,这样当下雨时,两个条之间收集的水是最大的.请注意,移除剩余的条后,条之间的距离保持不变.

例如:
1.[10,5,6,12,14] ans:30(10*3)
2.[3 16 10 5 6 12 20 18] ans:80(16*(16和18之间的整数) ).

有一个天真的O(N ²)解决方案,但我们可以做得更好吗？

Answer 1

使用堆栈可以解决这个问题,但是使用两个指针方法有一个更好更简单的解决方案.

这是伪代码:

result := 0
left := 0
right := n - 1
while(left < right):
    result := max(result, (right - left - 1) * min(arr[left], arr[right]))
    if(arr[left] <= arr[right]):
        left := left + 1
    else:
        right := right - 1
    endif
end

说明

从条的最左边和最右边的位置开始,并根据一些决定逐渐走向相反的方向,直到两个指针没有相互交叉.

什么时候arr[left] <= arr[right],我们会去,left := left + 1因为没有办法让更好的高度保持arr[left]为左边界.如果我们right := right - 1在这种情况下向左移动,则不可能在宽度上获得更大的区域,因为宽度将减小而高度将保持不变arr[left].

类似的逻辑arr[right] < arr[left].

时间复杂度O(n)和空间是O(1).

希望能帮助到你!