T42 接雨水

题目描述如下：

思路如下：

求出所包括雨水的整个矩形的面积，减去柱子的面积就是答案。从左到右处理方式是：

如果右边还有比当前位置大的，就加上当前位置的高度×(第一个大于该处的柱子的位置 - 当前的位置)，加完后当前位置是在第一个大于该位置的柱子的位置

如果没有，就找到在当前位置右边最大、最远（次要）的，总面积rectS加上当前位置高度 +（当前位置右边最大的、离当前位置最远的位置 - 当前位置 - 1）* 找到的柱子的高度，加完后i位置在找到的柱子处

结束条件为，当前位置柱子为最右边一个柱子

代码如下：

class Solution:
   def trap(self, height: List[int]) -> int:
       # 存储矩形信息
       length = len(height)
       rectS = 0
       i = 0
​
       # 计算矩形面积,i为当前位置
       while i < length:
           # 记录是否小于右边某个值,是则0，否则1
           rightbiggerflag = 1
           for j in range(i+1, length):
               # 如果存在小于右边某个值（第一个）
               if height[j] >= height[i]:
                   rectS += (j-i)*height[i]
                   i = j
                   rightbiggerflag = 0
                   break
                   
           # 如果右边没有比当前值更大的
           if rightbiggerflag ==1:
               # 结束条件
               if i == length - 1:
                   print("here")
                   rectS += height[i]
                   i += 1
                   break
               # 找到右边能达到的最大值
               rmax = height[i+1]
               rmaxindex = i+1
               for j in range(i+1, length):
                   if height[j] >= rmax:
                       rmax = height[j]
                       rmaxindex = j
               rectS += height[i] + (rmaxindex-i-1)*rmax
               i = rmaxindex              
       return rectS - sum(height)

结果如下：

慢的离谱

想了想优化方法：

列表索引换成字典，hash从来没有让我失望过！只需要在最前面将height列表存入mydic字典即可

当右边没有比当前更大的数的时候，需要对右边所有数每个都查找一遍，以找到最大最远的数。而如果右边有比当前更大的数时，就只需要找到比当前更大的数就可以停止了，而不用比较所有的数据，所以，如果将输入数据变成右边有至少一个不小于当前数的数的数据，应该可以减少很多次比较。

同时为了继续使用之前的代码，将之前的构造成jump函数，现在将数据分割之后调用两次就可以了。

代码如下：

class Solution:
   def trap(self, height: List[int]) -> int:
       def jump(lists: List[int]) -> int:
           # 存储矩形信息
           length = len(lists)
           rectS = 0
           i = 0
           mydict = {}
           for n in range(length):
               mydict[n] = lists[n]
           while i < length:
               # 判断是否到了右边
               rightflag = 1
               if i == length - 1:
                   rectS += mydict[i]
                   i += 1
                   break
               for j in range(i + 1, length):
                   if mydict[i] < mydict[j]:
                       rectS += (j - i) * mydict[i]
                       rightflag = 0
                       i = j
                       break
               if rightflag == 0:
                   continue
               else:
                   rmax = mydict[length - 1]
                   rmaxindex = length - 1
                   for j in range(i + 1, length):
                       if mydict[j] >= rmax:
                           rmax = mydict[j]
                           rmaxindex = j
                   rectS += mydict[i] + (rmaxindex - i - 1) * rmax
                   i = rmaxindex
           return rectS - sum(lists)
​
       maxnum = max(height)
       maxindex = height.index(maxnum)
       
       num1 = jump(height[:maxindex+1]) #计算从左边递增数据
       h = height[maxindex:]
       num2 = jump(h[::-1]) #计算从右边递增数据
       return num1+num2

结果如下：