根据图示，很容易得出 ：图2+图3-n*H_max-图1=图1装水面积。算法确实很精妙！
赞一个 谢谢各位的代码和 mahuan兄的图解，有趣的题目。
不过对各类算法不是很懂，问了一下儿子怎么解，他告诉我一句话：第n个挡板的蓄水值等于其左侧高度数列最大值A 和 其右侧高度数列最小值B 两者中的小值 减去n的高度值，加起来就可以。
像是奥数题。
估计原理和前面的代码也差不多。
验证了一下，好像如此：）
PY代码
a = ;s=0
for i in range(1,len(a)-1):
s=s+max(min(max(a),max(a))-a, 0)
print(s)
qjchen 发表于 2023-2-25 22:02
谢谢各位的代码和 mahuan兄的图解，有趣的题目。
不过对各类算法不是很懂，问了一下儿子怎么解，他告诉 ...
你这复杂度为O（N^2）了。图示算法为2*O（N）。 mahuan1279 发表于 2023-2-26 08:03
你这复杂度为O（N^2）了。图示算法为2*O（N）。
谢谢指出~
我这个写法确实不好，是n^2的。
也可以写为复杂度O(n)级别的，其中这个左右max是可以存储后每个对比下的，不过代码就长了，确实没有前面的精简。
页:
1
[2]