9/22 每日一題(找出list所組成的2維空間中最大的面積)

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

 

class Solution:

    def maxArea(self, height: List[int]) -> int:

        set_num=set(height)

        My_index_dict={}

        for i,n in enumerate(height):

            Index_list=My_index_dict.get(n,[])

            Index_list.append(i)

            My_index_dict[n]=Index_list

        sorter_dict=sorted(My_index_dict.items(),reverse=True)

        print(f'確認排序後的字典:{sorter_dict}')

        max_x=float('-inf')

        min_x=float('inf')

        max_area=0

        for i,j in sorter_dict:

            if len(j)>1:

                max_x=max(max_x,j[-1])

                min_x=min(min_x,j[0])

            else:

                max_x=max(max_x,j[0])

                min_x=min(min_x,j[0])

            width=max_x-min_x

            max_area=max(max_area,i*width)

            print(f'目前的長={i},寬={width},max_x={max_x}, min_x={min_x}')

            print(f'目前最大面積={max_area}')

        return max_area

-------------------------二分法

class Solution:
    def maxArea(self, height: List[int]) -> int:
        max_water = 0
        l,r = 0 , len(height) - 1
        h = max(height)

        while l < r :

            max_water = max(max_water , (min(height[l] , height[r]) * (r - l)))

            if height[l] >= height[r]:
                r -= 1
            else:
                l += 1

            if (r - l) * h <= max_water:
                break
            
        return max_water