Chris's Lab

If you obey all the rules,you miss all the fun.

0%

[LeetCode] 11. Container With Most Water

發表於 分類於 ， ， Disqus：
要如何找到可裝最多水的容器呢 (面積)

前言

　　這題是一個運用雙指標的算法，目標是找到可裝最多水的容器 (面積)，只需一個 while 迴圈就可依依遍歷到最大的面積答案，時間複雜度可估 O(n)，這裡有 JAVA 和 Python 的寫法。

題目

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]).
Find two lines that together with the x-axis form a container, such that the container contains the most water.
Return the maximum amount of water a container can store.
Notice that you may not slant the container.

給定一個長度為 n 的整數陣列 height ，畫了 n 條的垂直線，第 i 條線的兩個端點是 (i, 0) 和 (i, height[i])
找到兩條線與方向 x 軸一起形成的容器，使得這個容器包含最多的水
回傳可裝最大容量的水的容器
注意 你不行傾斜容器

題目連結：https://leetcode.com/problems/container-with-most-water/

題目限制

n == height.length
2 <= n <= 105
0 <= height[i] <= 104

範例

Container With Most Water 
1
2
3
Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: 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.
1
2
Input: height = [1,1]
Output: 1

思路&筆記

這題題目要我們做的是，在一個陣列裡取出兩個元素後，找出兩個元素相乘後的最大面積，使用的是雙指標算法。

  • 我們思考一下，算出容器的面積會需要的是高度和寬度
  • 設定高度，取用於陣列裡各個元素的值
  • 另一方面制定兩個指標，分別為 left 和 right，是要來代表容器的寬度
  • 並將 left = 0 作為寬度的起始點 (指標一)
  • 另外把 right = height.length - 1 作為寬度的結束點 (指標二)
  • 然後運用 while 遍歷陣列，來找出最大的容器
  • 如果 left 比 right 矮的時候，代表需要找到下一個比較高的容器高度，要 left++
  • 如果 right 比 left 矮的時候，代表需要找到前一個比較高的容器高度，要 left--
  • 如果 right 等於 left 的時候，代表前後一起作用把容器縮小，要 right++ 和 left--

[補充] 從矮牆開始取得，是因為裝水的時候基準會落在矮牆，超過矮牆的話水會溢出來，思考一下如果一個容器一邊高一邊低，水最多可以裝到哪? 當然最多只能裝到矮牆的最頂端，高牆就並不太重要了，取決於還是矮牆。

簡易示意圖

下述循環只演示到第三次，後續動作都是一樣的邏輯

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
8          |                             |
7          |                             |           |
6          |     |                       |           |
5          |     |           |           |           |
4          |     |           |     |     |           |
3          |     |           |     |     |     |     |
2          |     |     |     |     |     |     |     |
1    |     |     |     |     |     |     |     |     |
     0     1     2     3     4     5     6     7     8
    left                                           right

w = 8
h = 1
area = 8 * 1 = 8
max = 0 更新為 8
left < right，left++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
8          |                             |
7          |                             |           |
6          |     |                       |           |
5          |     |           |           |           |
4          |     |           |     |     |           |
3          |     |           |     |     |     |     |
2          |     |     |     |     |     |     |     |
1    |     |     |     |     |     |     |     |     |
     0     1     2     3     4     5     6     7     8
          left                                     right

w = 7
h = 7
area = 7 * 7 = 49
max = 8 更新為 49
left < right，right--
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
8          |                             |
7          |                             |           |
6          |     |                       |           |
5          |     |           |           |           |
4          |     |           |     |     |           |
3          |     |           |     |     |     |     |
2          |     |     |     |     |     |     |     |
1    |     |     |     |     |     |     |     |     |
     0     1     2     3     4     5     6     7     8
          left                               right

w = 6
h = 3
area = 6 * 3 = 18
max 不變，一樣是 49
left > right，left++

JAVA 實現

最簡單的是暴力解，就是把一個一個的面積遍歷出來比較，不過想當然兒送出結果跳出 Time Limit Exceeded 超過時間複雜度限制。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int maxArea(int[] height) {

        int max = 0; // 最大面積
        
        for (int i=0; i<height.length; i++){
            for (int j=i+1; j<height.length; j++){
                int erea = (j-i) * Math.min(height[i], height[j]); // 寬度 * 最小高度
                if (erea>max){
                    max = erea; // 設定最大面積
                }
            }
        }
        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
24
25
26
27
class Solution {
    public int maxArea(int[] height) {

        int left = 0; // 指標一
        int right = height.length - 1; // 指標二
        int max = 0; // 最大的面積

        while(left < right){

            int w = right - left; // 算出寬度
            int h = Math.min(height[left], height[right]); // 算出高度 (從最矮的開始)
            int area = h * w; // 算出面積
            max = Math.max(max, area); // 存入最大的面積

            if(height[left] < height[right]) {
                left++; // 找下一個比較大的元素
            }else if(height[left] > height[right]) {
                right--; // 找前一個比較大的元素
            }else {
                // 前後一起縮小
                left++;
                right--;
            }
        }
        return max;
    }
}

Python 實現

使用了和 Java 一樣的邏輯執行，換成 Python 的寫法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    def maxArea(self, height: List[int]) -> int:

        left = 0 # 指標一
        right = len(height) - 1 # 指標二
        max_area = 0 # 最大的面積

        while left < right:

            w = right - left # 算出寬度
            h = min(height[left], height[right]) # 算出高度 (從最矮的開始)
            area = w * h # 算出面積
            max_area = max(max_area, area) # 存入最大的面積

            if height[left] < height[right]:
                left += 1 # 找下一個比較大的元素
            elif height[left] > height[right]:
                right -= 1 # 找前一個比較大的元素
            else:
                # 前後一起縮小
                left += 1
                right -= 1

        return max_area

成績

Language Runtime Memory
Java 5ms 55.8MB
Python 744ms 28.4MB