Leetcode - Container With Most Water
2018 ワード
Leetcode : Container With Most Water
Given n non-negative integers a1, a2, ..., an , where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of the line i is at (i, ai) and (i, 0). Find two lines, which, together with the x-axis forms a container, such that the container contains the most water.
Example 1
Input
Input
Input
Input
Use two-pointer algorithm to calculate the maximum amount of water within the vertical lines. Set two variables left and right, and multiply smaller vertical line min(height[left], height[right]) to the number of spaces in between - (right - left)
Runtime: 152 ms
Memory Usage: 16.3 MB
Runtime Beats 61.64% of Python Submission
Description
Given n non-negative integers a1, a2, ..., an , where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of the line i is at (i, ai) and (i, 0). Find two lines, which, together with the x-axis forms a container, such that the container contains the most water.
Example 1
Input
height = [1,8,6,2,5,4,8,3,7]
Output49
Example 2Input
height = [1,1]
Output1
Example 3Input
height = [4,3,2,1,4]
Output16
Example 4Input
height = [1,2,1]
Output2
Approach
Use two-pointer algorithm to calculate the maximum amount of water within the vertical lines. Set two variables left and right, and multiply smaller vertical line min(height[left], height[right]) to the number of spaces in between - (right - left)
Solution (Python)
class Solution:
def maxArea(self, height: List[int]) -> int:
left = 0
right = len(height) - 1
maxArea = 0
while left < right:
maxArea = max(maxArea, (right - left) * min(height[left], height[right]))
if height[left] < height[right]:
left = left + 1
else:
right = right - 1
return maxArea
ResultRuntime: 152 ms
Memory Usage: 16.3 MB
Runtime Beats 61.64% of Python Submission
Reference
この問題について(Leetcode - Container With Most Water), 我々は、より多くの情報をここで見つけました https://velog.io/@jiselectric/Leetcode-Container-With-Most-Waterテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol