[leetcode algorithms]題目11

11. 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 line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Note: You may not slant the container and n is at least 2.

自己寫的代碼：

注意計算面積的思路是「木桶效應」。一開始用O(n^2)的寫法，遍歷所有的組合計算面積。結果超時了。試著尋找O(n)的演算法，讓i, j分別位於收尾，然後直到相遇。先挪動誰是本題的最關鍵點。用Update來判斷是否有必要更新面積，其實沒什麼用，並沒有縮短運行時間。最終運行時間133 ms

class Solution: def getArea(self, height, i, j): return (j - i) * min(height[i], height[j]) def maxArea(self, height): i = 0 j = len(height) - 1 res = self.getArea(height, i, j)# print(i, j) while i < j: if height[i] < height[j]: i += 1 update = height[i] > height[i - 1] else: j -= 1 update = height[j] > height[j + 1] if update: res = max(res, self.getArea(height, i, j))# print(i, j) return res

推薦閱讀：