愛比的新手筆記

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.

 

Example 1:

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.

Example 2:

Input: height = [1,1] Output: 1

 

Constraints:

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

一個直方圖要計算圍成的最大面積, 但不能跑雙迴圈去試, 會timout,
先以最左和最右圍成面積, 再以左右其中較小的優先往中間推進, 若是遇到更高的直方, 再算看看是否有更大面積

public int MaxArea(int[] height)
{
    int maxArea = 0;
    int high = 0;
    int i = 0;
    int j = height.Length - 1;
    do
    {
        int h = Math.Min(height[i], height[j]);
        if (h > high)
        {
            int area = h * (j - i);
            if (area >= maxArea)
            {
                maxArea = area;
                high = h;
            }
        }
        if (height[j] < height[i])
            j--;
        else
            i++;
    } while (i < j);
    return maxArea;
}

Taiwan is a country. 臺灣是我的國家