-
Notifications
You must be signed in to change notification settings - Fork 0
/
42 Trapping Rain Water .rtf
75 lines (74 loc) · 4.06 KB
/
42 Trapping Rain Water .rtf
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
{\rtf1\ansi\ansicpg1252\cocoartf2706
\cocoatextscaling0\cocoaplatform0{\fonttbl\f0\fnil\fcharset0 .SFNS-Regular_wdth_opsz120000_GRAD_wght1F40000;\f1\fnil\fcharset0 Menlo-Regular;}
{\colortbl;\red255\green255\blue255;\red29\green29\blue29;\red255\green255\blue255;\red0\green0\blue255;
\red0\green0\blue0;\red32\green108\blue135;\red101\green76\blue29;\red0\green0\blue109;\red19\green118\blue70;
\red157\green0\blue210;\red15\green112\blue1;}
{\*\expandedcolortbl;;\cssrgb\c14902\c14902\c14902;\cssrgb\c100000\c100000\c100000;\cssrgb\c0\c0\c100000;
\cssrgb\c0\c0\c0;\cssrgb\c14902\c49804\c60000;\cssrgb\c47451\c36863\c14902;\cssrgb\c0\c6275\c50196;\cssrgb\c3529\c52549\c34510;
\cssrgb\c68627\c0\c85882;\cssrgb\c0\c50196\c0;}
\margl1440\margr1440\vieww11520\viewh8400\viewkind0
\deftab720
\pard\pardeftab720\partightenfactor0
\f0\fs36 \cf2 \cb3 \expnd0\expndtw0\kerning0
\outl0\strokewidth0 \strokec2 42\'a0Trapping Rain Water
\f1\fs26 \cf4 \cb3 \strokec4 \
\pard\pardeftab720\partightenfactor0
\cf4 class\cf0 \strokec5 \cf6 \strokec6 Solution\cf0 \strokec5 :\cb1 \
\pard\pardeftab720\partightenfactor0
\cf0 \cb3 \cf4 \strokec4 def\cf0 \strokec5 \cf7 \strokec7 trap\cf0 \strokec5 (\cf8 \strokec8 self\cf0 \strokec5 , \cf8 \strokec8 height\cf0 \strokec5 : List[\cf6 \strokec6 int\cf0 \strokec5 ]) -> \cf6 \strokec6 int\cf0 \strokec5 :\cb1 \
\cb3 \cb1 \
\cb3 l,r = \cf9 \strokec9 0\cf0 \strokec5 , \cf7 \strokec7 len\cf0 \strokec5 (height)-\cf9 \strokec9 1\cf0 \cb1 \strokec5 \
\cb3 \cb1 \
\cb3 leftmax,rightmax=height[l],height[r]\cb1 \
\
\cb3 res=\cf9 \strokec9 0\cf0 \cb1 \strokec5 \
\
\cb3 \cf10 \strokec10 while\cf0 \strokec5 l < r:\cb1 \
\cb3 \cf10 \strokec10 if\cf0 \strokec5 leftmax<rightmax:\cb1 \
\cb3 l+=\cf9 \strokec9 1\cf0 \cb1 \strokec5 \
\cb3 leftmax=\cf7 \strokec7 max\cf0 \strokec5 (height[l],leftmax)\cb1 \
\cb3 res+= leftmax - height[l]\cb1 \
\cb3 \cf10 \strokec10 else\cf0 \strokec5 :\cb1 \
\cb3 r-=\cf9 \strokec9 1\cf0 \cb1 \strokec5 \
\cb3 rightmax=\cf7 \strokec7 max\cf0 \strokec5 (height[r],rightmax)\cb1 \
\cb3 res+=rightmax-height[r]\cb1 \
\cb3 \cb1 \
\cb3 \cf10 \strokec10 return\cf0 \strokec5 res\cb1 \
\
\
\
\
\cb3 \cf11 \strokec11 # lM = 0\cf0 \cb1 \strokec5 \
\cb3 \cf11 \strokec11 # leftmax=[]\cf0 \cb1 \strokec5 \
\cb3 \cf11 \strokec11 # rm=0\cf0 \cb1 \strokec5 \
\cb3 \cf11 \strokec11 # rightmax=[]\cf0 \cb1 \strokec5 \
\cb3 \cb1 \
\cb3 \cf11 \strokec11 # for n in height:\cf0 \cb1 \strokec5 \
\cb3 \cf11 \strokec11 # leftmax.append(lM)\cf0 \cb1 \strokec5 \
\cb3 \cf11 \strokec11 # lM=max(lM,n)\cf0 \cb1 \strokec5 \
\cb3 \cf11 \strokec11 # #print(leftmax)\cf0 \cb1 \strokec5 \
\
\cb3 \cf11 \strokec11 # for n in height[::-1]:\cf0 \cb1 \strokec5 \
\cb3 \cf11 \strokec11 # rightmax.append(rm)\cf0 \cb1 \strokec5 \
\cb3 \cf11 \strokec11 # rm=max(rm,n)\cf0 \cb1 \strokec5 \
\cb3 \cf11 \strokec11 # rightmax.reverse()\cf0 \cb1 \strokec5 \
\cb3 \cf11 \strokec11 # #print(rightmax)\cf0 \cb1 \strokec5 \
\
\cb3 \cf11 \strokec11 # minlorr=[]\cf0 \cb1 \strokec5 \
\cb3 \cf11 \strokec11 # for i in range(len(rightmax)):\cf0 \cb1 \strokec5 \
\cb3 \cf11 \strokec11 # minlorr.append(min(leftmax[i],rightmax[i]))\cf0 \cb1 \strokec5 \
\
\cb3 \cf11 \strokec11 # res,ans=0,0\cf0 \cb1 \strokec5 \
\
\cb3 \cf11 \strokec11 # for i in range(len(height)):\cf0 \cb1 \strokec5 \
\cb3 \cf11 \strokec11 # ans = minlorr[i] - height[i]\cf0 \cb1 \strokec5 \
\cb3 \cf11 \strokec11 # if ans>0:\cf0 \cb1 \strokec5 \
\cb3 \cf11 \strokec11 # res+=ans\cf0 \cb1 \strokec5 \
\cb3 \cf11 \strokec11 # ans=0\cf0 \cb1 \strokec5 \
\
\cb3 \cf11 \strokec11 # return res\cf0 \cb1 \strokec5 \
\cb3 \cb1 \
\cb3 \cf11 \strokec11 #print(minlorr)\cf0 \cb1 \strokec5 \
\cb3 \cf11 \strokec11 # return 0\cf0 \cb1 \strokec5 \
\
}