LeetCode-Container With Most Water

The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.

Container With Most Water解法分享

問題

原文在下面,題目大意是,給一組非負整數的陣列,並且可以對應到座標圖上。陣列的index為x軸作標,值則為y坐標,依照給定的陣列就可以畫出長條圖。

在這長條圖中,每兩條線都可以形成一個容器,並找出最大的容量。依照所給的例子,形成最大容量的兩條線分別是 [2,8] [9,7] ,容量為49。

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.

解法

第一種是暴力破解法(Brute Force),這個就不多做解釋了,一開始我也是用暴力破解法(汗顏),附上LeetCode給的 java code。

# java
public class Solution {
public int maxArea(int[] height) {
int maxarea = 0;
for (int i = 0; i < height.length; i++)
for (int j = i + 1; j < height.length; j++)
maxarea = Math.max(maxarea, Math.min(height[i], height[j]) * (j - i));
return maxarea;
}
}

第二種解法是Two Pointer Approach,先附上筆者用ruby寫的解法。

# ruby
def max_area(height)
max_area = 0
left = 0
right = height.length - 1
while left < right
h = height[left] > height[right] ? height[right] : height[left]
w = right - left
area = h * w
max_area = area if area > max_area
if height[left] > height[right]
right = right - 1
else
left = left + 1
end
end
return max_area
end

想法

Two Pointer Approach先簡稱TPA好了,TPA的解法步驟為

  1. 初始化最大面積(max_area)以及右邊(right)、左邊(left)的線,left為0,right則為陣列長度-1
  2. 由於容器是以裝水為前提,所以高度為較短的線,長度則為 right — left ,算出面積,若面積大於max_area,則取代max_area
  3. 比較兩條線的高度,若左邊較小,則左邊的線往右移 left + 1,反之則右邊的線往左移 right — 1
  4. 回步驟二,直到兩條線交錯

一開始看到TPA的解法時,無法理解為何這樣可以保證比較過所有的容器面積,並且得到的結果是正確的,後來看到別人分享的想法,才真的理解這個解法的精髓,以下分享該觀點。

以矩陣形式來表達這個問題的話,列(row)代表左邊的線,欄(column)代表右邊的線,x代表不需要計算的面積,例如(1,1),因為兩條線重疊,而下方左邊x組成的三角形部分會跟右上相同,因此也不需要做計算。

以TPA的步驟來看,會先計算最左邊以及最右邊的線組成的容器面積,也就是(1,6)以o來做表示,假設左邊的線小於右邊的線,則所有在(1,6)左邊的值都會小於o,因此以 — 來表示不需計算。

以最一開始的例子 [1,8,6,2,5,4,8,3,7]來舉例,(1,8)的面積為8,而1<8,所以在(1,8)左邊的面積,分別是1,2,3,4,5,6,7,都會小於8。

  1 2 3 4 5 6
1 x - - - - o
2 x x
3 x x x
4 x x x x
5 x x x x x
6 x x x x x x

將左邊的線往右移,此時算出(2,6)的值,這邊假設右邊的線小於左邊,則在(2,6)下方的值皆可以去除不去計算。以一開始的例子來說(2,8)的面積為49,若以該例子列出矩陣,並算出(2,8)下方其餘點的面積,都會小於49。

  1 2 3 4 5 6
1 x - - - - o
2 x x o
3 x x x |
4 x x x x |
5 x x x x x |
6 x x x x x x

依照這個步驟持續下去,就可以得到最大的面積,其時間複雜度為 O(n)。

  1 2 3 4 5 6
1 x ------- o
2 x x - o o o
3 x x x o | |
4 x x x x | |
5 x x x x x |
6 x x x x x x

通過矩陣的圖像表示後,筆者是認為比較容易理解TPA的運作模式,若有不清楚之處,歡迎發問或者參考原文。

參考

https://leetcode.com/problems/container-with-most-water/discuss/6099/yet-another-way-to-see-what-happens-in-the-on-algorithm