挡墙蓄水 算法实现

landsat99

mahuan1279 发表于 2023-2-24 10:27
根据图示，很容易得出 ：图2+图3-n*H_max-图1=图1装水面积。算法确实很精妙！

赞一个

qjchen

谢谢各位的代码和 mahuan兄的图解，有趣的题目。

不过对各类算法不是很懂，问了一下儿子怎么解，他告诉我一句话：第n个挡板的蓄水值等于其左侧高度数列最大值A 和 其右侧高度数列最小值B 两者中的小值 减去n的高度值，加起来就可以。
像是奥数题。

估计原理和前面的代码也差不多。
验证了一下，好像如此：）


PY代码

1. a = [0, 1, 5, 12, 7, 11, 3, 5, 12, 14, 16, 6, 4, 12, 9, 23, 16, 4, 13, 8, 12, 15, 7, 8, 4];s=0
   
2. for i in range(1,len(a)-1):
   
3.   s=s+max(min(max(a[0:i]),max(a[i+1:len(a)]))-a[i], 0)
   
4. print(s)

复制代码

mahuan1279

qjchen 发表于 2023-2-25 22:02
谢谢各位的代码和 mahuan兄的图解，有趣的题目。

不过对各类算法不是很懂，问了一下儿子怎么解，他告诉 ...

你这复杂度为O（N^2）了。图示算法为2*O（N）。

qjchen

mahuan1279 发表于 2023-2-26 08:03
你这复杂度为O（N^2）了。图示算法为2*O（N）。

谢谢指出~
我这个写法确实不好，是n^2的。
也可以写为复杂度O(n)级别的，其中这个左右max是可以存储后每个对比下的，不过代码就长了，确实没有前面的精简。