首页 > 代码库 > #LeetCode# Container With Most Water （todo）
#LeetCode# Container With Most Water （todo）
描述：
实现1 -- 求所有可能的值，O（N^2)，超时了（因为超时没有跑所有的测试用例，所以不确定还有没有其他问题）
代码：
1 def maxArea(self, height): 2 tmp = len(height) 3 if tmp == 0 or tmp == 1: return 0 4 if tmp == 2: return abs(height[1] - height[0]) 5 6 minus_lst = [height[i] - height[i-1] for i in range(1, len(height))] 7 # len(minus_lst) >= 2 8 9 dis, max, l = 2, 0, len(minus_lst)10 11 while True:12 for i in range(l):13 if i + dis > l: break14 15 area = abs(sum(minus_lst[i:i+dis]) * dis)16 if area > max: max = area 17 18 dis += 119 if dis > l: break20 21 return max
实现2：
对于每一个节点，取比他长的节点的位置，此时area = 距离差 * 这个节点的高度，实践复杂度 O(N^2)，超时
代码：
1 def maxArea(self, height): 2 tmp = len(height) 3 result = 0 4 5 for i in range(tmp): 6 for j in range(tmp): 7 if height[j] >= height[i]: 8 area = height[i] * abs(i - j) 9 if area > result: result = area10 11 return result
优化-1 依然超时
1 def maxArea(self, height): 2 tmp = len(height) 3 result = 0 4 5 record = [] 6 for i in range(tmp): 7 for j in range(tmp): 8 if height[j] >= height[i]: 9 record.append(abs(j - i))10 area = height[i] * max(record)11 if area > result: result = area12 record = []13 14 return result
优化-2 超时
1 def maxArea(self, height): 2 tmp = len(height) 3 result = 0 4 5 for i in range(tmp): 6 t = None 7 for j in range(i): 8 if height[j] > height[i]: 9 t = abs(j - i)10 break11 12 if t is not None:13 area_1 = t * height[i]14 if area_1 > result: result = area_115 16 t = None17 for j in range(i, tmp)[::-1]:18 if height[j] > height[i]:19 t = abs(j - i)20 break21 22 if t is not None:23 area_2 = t * height[i]24 if area_2 > result: result = area_225 26 return result
实现3
从左端点和右端点开始，贪婪，不断取小的值推进，符合直觉，如何证明可以使用贪婪
当左边是i右边是j时，ij之间不会有更大的，两边？
todo
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。