問(wèn)題描述

給定一個(gè)長(zhǎng)度為 n 的整數(shù)數(shù)組 height 。有n條垂線，第i條線的兩個(gè)端點(diǎn)是(i, 0)和(i, height[i])。
找出其中的兩條線，使得它們與 x 軸共同構(gòu)成的容器可以容納最多的水。
返回容器可以儲(chǔ)存的最大水量。
說(shuō)明：你不能傾斜容器。

示例1

輸入：[1,8,6,2,5,4,8,3,7]
輸出：49
解釋：圖中垂直線代表輸入數(shù)組 [1,8,6,2,5,4,8,3,7]。在此情況下，容器能夠容納水（表示為藍(lán)色部分）的最大值為 49。

示例2

輸入：height = [1,1]
輸出：1

提示

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

思路分析

1. 首先，我們定義了一個(gè)Solution類，其中包含解決問(wèn)題的方法maxArea。
2. 方法maxArea接收一個(gè)整數(shù)數(shù)組height作為參數(shù)。
3. 我們通過(guò)雙指針來(lái)解決這個(gè)問(wèn)題。左指針left初始化為數(shù)組的第一個(gè)元素下標(biāo)0，右指針right初始化為數(shù)組最后一個(gè)元素的下標(biāo)n-1。
4. 初始化最大面積max_area為0。
5. 進(jìn)入循環(huán)，條件是左指針小于右指針。這是因?yàn)楫?dāng)左指針和右指針相遇時(shí)，無(wú)法再構(gòu)成有效的容器。
6. 在每一次循環(huán)中，我們計(jì)算當(dāng)前的面積curr_area。面積的計(jì)算公式是兩個(gè)指針?biāo)父叨容^小值乘以兩個(gè)指針之間的距離即(right - left)。
7. 更新最大面積max_area，通過(guò)將當(dāng)前面積curr_area與max_area比較，如果curr_area更大，則更新max_area。
8. 接下來(lái)，根據(jù)以下三種情況移動(dòng)指針：
   • 如果height[left]小于height[right]，那么我們將左指針left向右移動(dòng)一位，即left += 1，因?yàn)橐苿?dòng)左指針不能增加當(dāng)前的面積。
   • 如果height[left]大于height[right]，那么我們將右指針right向左移動(dòng)一位，即right -= 1，因?yàn)橐苿?dòng)右指針不能增加當(dāng)前的面積。
   • 如果height[left]等于height[right]，那么我們既可以移動(dòng)左指針也可以移動(dòng)右指針。在這種情況下，無(wú)論移動(dòng)哪個(gè)指針，都不會(huì)改變當(dāng)前的面積。
9. 循環(huán)結(jié)束后，返回最大面積max_area作為結(jié)果。

這種解決方法的核心思想是通過(guò)不斷縮小有效寬度的范圍，來(lái)尋找容器的最大面積。通過(guò)比較較小高度的指針向內(nèi)移動(dòng)，可以保留更有可能得到更大面積的高度。最終，我們得到了兩條垂線所形成容器的最大面積。

代碼分析

1. 首先，我們定義了一個(gè)Solution類。
2. 在類中，我們定義了一個(gè)方法maxArea，它接收一個(gè)整數(shù)數(shù)組height作為參數(shù)。
3. 我們首先獲取數(shù)組height的長(zhǎng)度n，用于后續(xù)循環(huán)的條件判斷。
4. 初始化左指針left為0，右指針right為數(shù)組最后一個(gè)元素的下標(biāo)n-1。
5. 初始化最大面積max_area為0。
6. 進(jìn)入循環(huán)，條件是左指針left小于右指針right。
7. 在循環(huán)中，我們計(jì)算當(dāng)前的面積curr_area，即兩個(gè)指針?biāo)父叨容^小值乘以兩個(gè)指針之間的距離，使用min()函數(shù)取得較小值。
8. 更新最大面積max_area，通過(guò)將當(dāng)前面積curr_area與max_area比較，并將較大值賦給max_area，用max()函數(shù)實(shí)現(xiàn)。
9. 接下來(lái)，使用三個(gè)判斷條件來(lái)決定指針的移動(dòng)：
   • 如果height[left]小于height[right]，說(shuō)明左指針指向的高度較低，移動(dòng)左指針left向右移動(dòng)一位，即left += 1。
   • 如果height[left]大于height[right]，說(shuō)明右指針指向的高度較低，移動(dòng)右指針right向左移動(dòng)一位，即right -= 1。
   • 如果height[left]等于height[right]，說(shuō)明兩邊的高度相等，無(wú)論左指針left還是右指針right都可以移動(dòng)，所以同時(shí)將左指針left向右移動(dòng)一位，即left += 1，右指針right向左移動(dòng)一位，即right -= 1。
10. 循環(huán)結(jié)束后，返回最大面積max_area作為結(jié)果。

完整代碼

class Solution(object):
    def maxArea(self, height):
        n = len(height)  # 獲取數(shù)組height的長(zhǎng)度n
        left, right = 0, n - 1  # 初始化左指針left為0，右指針right為數(shù)組最后一個(gè)元素的下標(biāo)n-1
        max_area = 0  # 初始化最大面積max_area為0

        while left < right:  # 進(jìn)入循環(huán)，條件是左指針left小于右指針right
            curr_area = min(height[left], height[right]) * (right - left)  # 計(jì)算當(dāng)前的面積curr_area，即兩個(gè)指針?biāo)父叨容^小值乘以兩個(gè)指針之間的距離
            max_area = max(max_area, curr_area)  # 更新最大面積max_area，通過(guò)將當(dāng)前面積curr_area與max_area比較，并將較大值賦給max_area

            if height[left] < height[right]:  # 如果height[left]小于height[right]
                left += 1  # 移動(dòng)左指針left向右移動(dòng)一位
            elif height[left] > height[right]:  # 如果height[left]大于height[right]
                right -= 1  # 移動(dòng)右指針right向左移動(dòng)一位
            else:  # 如果height[left]等于height[right]
                left += 1  # 同時(shí)移動(dòng)左指針left向右移動(dòng)一位
                right -= 1  # 同時(shí)移動(dòng)右指針right向左移動(dòng)一位
        
        return max_area  # 返回最大面積max_area作為結(jié)果

詳細(xì)分析

1. 首先定義一個(gè)名為Solution的類。

class Solution(object):

2. 然后，我們?cè)赟olution類中定義了一個(gè)名為maxArea的方法，該方法接收一個(gè)名為height的參數(shù)。

    def maxArea(self, height):

3. 在方法體內(nèi)部，我們獲取數(shù)組height的長(zhǎng)度，并將結(jié)果賦給變量n。

        n = len(height)

4. 接下來(lái)，我們初始化左指針left為0，右指針right為數(shù)組最后一個(gè)元素的下標(biāo)n-1。

        left, right = 0, n - 1

5. 我們還定義了一個(gè)變量max_area，并將其初始化為0，用于保存最大面積的值。

        max_area = 0

6. 在接下來(lái)的while循環(huán)中，我們判斷左指針是否小于右指針，如果是，則執(zhí)行循環(huán)體內(nèi)的代碼。

        while left < right:

7. 在循環(huán)體內(nèi)部，我們首先計(jì)算當(dāng)前的面積curr_area，即兩個(gè)指針?biāo)父叨容^小值乘以兩個(gè)指針之間的距離。

            curr_area = min(height[left], height[right]) * (right - left)

8. 接著，我們更新最大面積max_area，通過(guò)將當(dāng)前面積curr_area與max_area比較，并將較大值賦給max_area。

            max_area = max(max_area, curr_area)

9. 然后，我們根據(jù)左指針和右指針指向的高度來(lái)移動(dòng)指針。

• 如果左指針指向的高度小于右指針指向的高度，則將左指針向右移動(dòng)一位。

            if height[left] < height[right]:
                left += 1

• 如果左指針指向的高度大于右指針指向的高度，則將右指針向左移動(dòng)一位。

            elif height[left] > height[right]:
                right -= 1

• 如果左指針指向的高度等于右指針指向的高度，則同時(shí)將左指針向右移動(dòng)一位，并將右指針向左移動(dòng)一位。

            else:
                left += 1
                right -= 1

10. 循環(huán)結(jié)束后，我們返回最大面積max_area作為結(jié)果。

        return max_area

運(yùn)行效果截圖

調(diào)用示例

solution = Solution()
x = [1,8,6,2,5,4,8,3,7]
x1 = [1,1]
print(solution.maxArea(x))
print(solution.maxArea(x1))

運(yùn)行結(jié)果

完結(jié)

文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-562378.html

到了這里，關(guān)于【力扣算法12】之 11. 盛最多水的容器 python的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！