C語言重構【11】盛最多水的容器

文章目錄

所有題目源代碼：Git地址

題目

給你 n 個非負整數 a1，a2，…，an，每個數代表坐標中的一個點 (i, ai) 。在坐標內畫 n 條垂直線，垂直線 i 的兩個端點分別為 (i, ai) 和 (i, 0)。找出其中的兩條線，使得它們與 x 軸共同構成的容器可以容納最多的水。

說明：你不能傾斜容器，且 n 的值至少為 2。

在這里插入圖片描述

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

示例：
輸入：[1,8,6,2,5,4,8,3,7]
輸出：49

方案：

class Solution
{
public:
    int maxArea(vector<int> &height)
    {
        int left = 0, right = height.size() - 1;
        int area = 0;

        while(left<right){
            area = max(area,min(height[right],height[left])*(right-left));
            int newarea = (height[right]<height[left]?height[right]:height[left])*(right-left);
            area = area>newarea?area:newarea;
            if (height[left]<height[right])
            {
                left++;
            }
            else{
                right--;
            }
        }
        return area;
    }
};

復雜度計算

時間復雜度：O(n)
空間復雜度：O(1)

本文鏈接：https://blog.csdn.net/symuamua/article/details/108648389

智能推薦

leetcode#11盛最多水的容器（C語言實現）

leetcode#11盛最多水的容器（C語言實現）題目描述：給你 n 個非負整數 a1，a2，…，an，每個數代表坐標中的一個點 (i, ai) 。在坐標內畫 n 條垂直線，垂直線 i 的兩個端點分別為 (i, ai) 和 (i, 0)。找出其中的兩條線，使得它們與 x 軸共同構成的容器可以容納最多的水。說明：你不能傾斜容器，且 n 的值至少為 2。示例：輸入：[1,8,6,...

LeetCode第11題盛最多水的容器C語言實現

LeetCode第11題盛最多水的容器C語言實現 leetcode原題地址題目描述示例：輸入：[1,8,6,2,5,4,8,3,7] 輸出：49 題解 1.暴力**方法把所有可能的結果求出來，返回最大的值，代碼如下：執行結果如下：該算法時間復雜度為O(n^2) 2.雙指針法運行結果如下：該算法時間復雜為O(n) 雙指針法總結：從最左邊一個元素和最右邊一個元素向中間遞歸求面積，如果...

LeetCode:11. Container With Most Water 盛最多水的容器（C語言）

題目描述：給定 n 個非負整數 a1，a2，…，an，每個數代表坐標中的一個點 (i, ai) 。在坐標內畫 n 條垂直線，垂直線 i 的兩個端點分別為 (i, ai) 和 (i, 0)。找出其中的兩條線，使得它們與 x 軸共同構成的容器可以容納最多的水。說明：你不能傾斜容器，且 n 的值至少為 2。圖中垂直線代表輸入數組 [1,8,6,2,5,4,8,3,7]。在此情況下，容...

【C語言刷LeetCode】11. 盛最多水的容器（M）

[ 給定 n 個非負整數 a1，a2，...，an，每個數代表坐標中的一個點 (i, ai) 。在坐標內畫 n 條垂直線，垂直線 i 的兩個端點分別為 (i, ai) 和 (i, 0)。找出其中的兩條線，使得它們與 x 軸共同構成的容器可以容納最多的水。說明：你不能傾斜容器，且 n 的值至少為 2。圖中垂...

LeetCode：盛最多水的容器【11】

LeetCode：盛最多水的容器【11】題目描述給定 n 個非負整數 a1，a2，...，an，每個數代表坐標中的一個點 (i, ai) 。在坐標內畫 n 條垂直線，垂直線 i 的兩個端點分別為 (i, ai) 和 (i, 0)。找出其中的兩條線，使得它們與 x 軸...