容器盛水问题

[编程题]容器盛水问题

热度指数：4928 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个整形数组arr，已知其中所有的值都是非负的，将这个数组看作一个容器，请返回容器能装多少水。

具体请参考样例解释

输入描述:

第一行一个整数N，表示数组长度。

接下来一行N个数表示数组内的数。

输出描述:

输出一个整数表示能装多少水。

示例1

输入

6
3 1 2 5 2 4

输出

说明

示例2

输入

5
4 5 1 3 2

输出

备注:

算法知识视频讲解

Python

汤普森30

N = int(input())
nums = list(map(int, input().split()))

res = 0
maxH = max(nums)
idx = nums.index(maxH)
leftH,rightH = 0, 0
for i in range(idx):
    if nums[i] < leftH:
        res += (leftH - nums[i])
    else:
        leftH = nums[i]
for i in range(N-1, idx, -1):
    if nums[i] < rightH:
        res += (rightH - nums[i])
    else:
        rightH = nums[i]
print(res)

发表于 2019-08-29 16:33:34 回复(0)