未分類

Container With Most Water

Array, Go, LeetCode, TwoPointers

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.

提示 解題應用
Array Array/Slice
TwoPointers 紀錄index位置

Default:

1
2
3
func maxArea(height []int) int {
}

解答思路:

從一陣列中挑兩個隔板，其中index值為隔板放置的位置，其值則為隔板的高度，找出兩個隔板能圍出的最大面積，最初先嘗試使用暴力法而超時，其實只要從分邊從兩邊同時判斷並分別向中間前進尋找即可，在一開始時從最左邊與最右邊拿到隔板，因為此時相距最遠所以圍出來的面積長度當然就最長，剩下的就只有高度的問題，兩個隔板如果不一樣高的話，水當然只能裝到比較矮的地方，在算出長方形面積(隔板間距*較矮的高度)後，之後就要考慮如何向內找隔板才能找出最大值，因為向內會使隔板間距離縮短，所以如果找的不是比較高的隔板就沒意義，此時在最左與最右的兩隔板中，選擇比較矮的那邊往內一格換較內側的隔板，算出面積並比較是否為最大之後就再次重覆上述比較動作，直到找出所有能圍出最大面積的可能。

程式碼解說:

一開始先初始化要拿最左右兩側的隔板，接著才開始不斷尋找最大面積直到拿到左側隔板的位置超過右側為止，如果右側隔板的高度比較高，此時先計算面積並從較矮的左側一方，向內找更高的隔板，反之如果是右側較高則右側從右側一方往內找更高的隔板，最後才比較先前找出的面積是否大於最大值，如果是就將其取代，直到找出所有能圍出最大面積的可能才回傳其中的最大值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
var max int
var area int
left := 0
right := len(height) - 1
hl := height[left]
hr := height[right]
for left < right {
	if hl < hr {
		area = hl * (right - left)
		left++
		hl = height[left]
	} else {
		area = hr * (right - left)
		right--
		hr = height[right]
	}
	if area > max {
		max = area
	}
}
return max

完整程式碼:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func maxArea(height []int) int {
	var max int
	var area int
	left := 0
	right := len(height) - 1
	hl := height[left]
	hr := height[right]
	for left < right {
		if hl < hr {
			area = hl * (right - left)
			left++
			hl = height[left]
		} else {
			area = hr * (right - left)
			right--
			hr = height[right]
		}
		if area > max {
			max = area
		}
	}
	return max
}

總結:

從一陣列中挑兩個隔板，其中index值為隔板放置的位置，其值則為隔板的高度，找出兩個隔板能圍出的最大面積，在一開始時從最左邊與最右邊拿到隔板並計算面積，之後在最左與最右的兩隔板中，選擇比較矮的那邊往內一格換較內側的隔板，算出面積並比較是否為最大之後就再次重覆上述比較動作，直到找出所有能圍出最大面積的可能。

分享到