挡墙蓄水 算法实现

landsat99

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

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

         - 试算 List = [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]，可蓄水多少？

示意图：

mahuan1279

_$ (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

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

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

1. id = 0
   
2. area = 0
   
3. max_List = 0
   
4. for i in range(len(List)):
   
5.     h = List[i]
   
6.     if h > max_List:
   
7.         max_List = h
   
8.         id = i
   
9. tmp = List[0]  # 左侧循环
   
10. for i in range(id):
    
11.     if List[i] > tmp:
    
12.         tmp = List[i]
    
13.     else:
    
14.         area = area + (tmp - List[i])
    
15. tmp = List[-1]  # 右侧循环
    
16. for i in reversed(range(id + 1, len(List))):
    
17.     if List[i] > tmp:
    
18.         tmp = List[i]
    
19.     else:
    
20.         area = area + (tmp - List[i])
    
21. print(area)
    

复制代码

结果：
>> 79

笨笨熊007

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

mahuan1279

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

landsat99

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

赞一个

landsat99

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

算法如下：

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

1. ans = 0; h1 = 0; h2 = 0
   
2. for i in range(len(List)):
   
3.     h1 = max(h1, List[i])
   
4.     h2 = max(h2, List[-i - 1])
   
5.     ans = ans + h1 + h2 - List[i]
   
6. print(ans - len(List) * h1)

复制代码

结果：
>> 79

mahuan1279

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

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

算法如下：

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

mahuan1279

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