社区 › 几何算法 › 挡墙蓄水 算法实现

landsat99 发表于 2023-2-19 18:42:02

挡墙蓄水 算法实现

本帖最后由 landsat99 于 2023-2-19 18:48 编辑

描述：每块挡板的宽度为W=1；高度为 Hi。多块挡板 Hi 组成有序列表 List.

问题：此List高度排列的挡板，最多能蓄多少水，及算法实现。

         - 试算 List = ，可蓄水多少？

示意图：

mahuan1279 发表于 2023-2-20 23:30:50

_$ (defun f(lst)
(setq list_max (apply 'max lst) len (length lst))
(setq flst (mapcar '(lambda (x) (if (= x list_max) 1 0)) lst))
(setq nl (vl-position 1 flst) nr (vl-position 1 (reverse flst)))
(setq i 0 j 0 s 0 l_max 0 r_max 0 llst (reverse lst))
(while (< i nl)
(setq l_now (nth i lst))
(if (> l_now l_max)
   (setq l_max l_now)
       (setq s (+ s (- l_max l_now)))
)
(setq i (+ i 1))
)
(while (< j nr)
(setq r_now (nth j llst))
(if (> r_now r_max)
   (setq r_max r_now)
       (setq s (+ s (- r_max r_now)))
)
(setq j (+ j 1))
)
(while (< i (- len nl nr))
(setq l_now (nth i lst))
(setq s (+ s (- list_max l_now)))
(setq i (+ i 1))
)
s
)
F

_$ (f '(0 1 0 2 1 0 1 3 2 1 2 1))
6
_$ (f '(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))
79
_$

landsat99 发表于 2023-2-21 17:47:28

本帖最后由 landsat99 于 2023-2-21 18:12 编辑

尝试
算法一：求极值 --> 左右分别累加 --> 总和。

与楼上大咖的lisp算法基本相同.

id = 0
area = 0
max_List = 0
for i in range(len(List)):
    h = List
    if h > max_List:
      max_List = h
      id = i
tmp = List# 左侧循环
for i in range(id):
    if List > tmp:
      tmp = List
    else:
      area = area + (tmp - List)
tmp = List[-1]# 右侧循环
for i in reversed(range(id + 1, len(List))):
    if List > tmp:
      tmp = List
    else:
      area = area + (tmp - List)
print(area)

结果：
>> 79

笨笨熊007 发表于 2023-2-19 18:47:11

力扣算法有原题，可以参考下

mahuan1279 发表于 2023-2-20 08:51:30

左右双指针，面积累加求和。

landsat99 发表于 2023-2-21 17:36:13

mahuan1279 发表于 2023-2-20 23:30
_$ (defun f(lst)
(setq list_max (apply 'max lst) len (length lst))
(setq flst (mapcar '(lambda (x) ...

赞一个

landsat99 发表于 2023-2-21 17:55:16

本帖最后由 landsat99 于 2023-2-21 18:16 编辑

另外，见到一个神回复。采用单循环，重复后减除的方法。

算法如下：

不过，个人对此持谨慎态度。较容易弄错。。。虽然代码相当简洁

ans = 0; h1 = 0; h2 = 0
for i in range(len(List)):
    h1 = max(h1, List)
    h2 = max(h2, List[-i - 1])
    ans = ans + h1 + h2 - List
print(ans - len(List) * h1)
结果：
>> 79

mahuan1279 发表于 2023-2-21 19:02:37

landsat99 发表于 2023-2-21 17:55
另外，见到一个神回复。采用单循环，重复后减除的方法。

算法如下：


运行结果是对的，但还没搞清去重原理。
_$ (defun ff(lst)
(setq len (length lst) i 0 area 0 h1 0 h2 0)
(while (< i len)
   (setq h1 (max h1 (nth i lst)))
   (setq h2 (max h2 (nth (- len i 1) lst)))
   (setq area (- (+ area h1 h2) (nth i lst)))
   (setq i (+ i 1))
)
(setq area (- area (* h1 len)))
)
FF
_$(ff '(0 1 0 2 1 0 1 3 2 1 2 1))
6
_$ (ff '(3 1 2))
1
_$ (ff '( 3 3 1 2))
1
_$ (ff '( 3 3 1 2 3))
3
_$ (ff '( 3 3 5 3))
0
_$ (ff '(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))
79
_$

mahuan1279 发表于 2023-2-24 08:22:47

landsat99 发表于 2023-2-21 17:55
另外，见到一个神回复。采用单循环，重复后减除的方法。

算法如下：


这个算法有没有出处？简单分析了123六种排列顺序，结果都是对的。估计是根据类似归纳法延推至任意列表都成立吧。

mahuan1279 发表于 2023-2-24 10:27:50

根据图示，很容易得出 ：图2+图3-n*H_max-图1=图1装水面积。算法确实很精妙！

查看完整版本: 挡墙蓄水 算法实现