iT邦幫忙

2021 iThome 鐵人賽

DAY 9
0
自我挑戰組

30天 Leetcode解題之路系列 第 9

Day 9 - Container With Most Water

大家好,我是毛毛。ヾ(´∀ ˋ)ノ
廢話不多說開始今天的解題Day~


11. Container With Most Water

Question

Given n non-negative integers a1, a2, ..., an , where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of the line i is at (i, ai) and (i, 0). Find two lines, which, together with the x-axis forms a container, such that the container contains the most water.

Notice that you may not slant the container.


Example

Example1

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.

Example2

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

Example3

Input: height = [4,3,2,1,4]
Output: 16

Example4

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

Constraints

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

解題

題目

首先先簡單的翻譯一下題目
給一個陣列,每一個元素分別代表高度,從陣列中找兩個元素,當成容器的左右兩側,計算包圍起來的面積大小,找最大面積,面積計算方式不會是梯形!

Think

作法大致上是這樣

  • 一開始是用兩層for loop暴力解,但是解陣列長度過長的測資時,會跑超過時間限制。
  • 就稍微改寫了一下,用一層迴圈解解看,用leftright兩個變數指向容器左右兩側的位址,用min取左右兩側的低值,乘上right-left(寬),最後跟目前的最大面積取max
  • height[left] > height[right]right -= 1,這是因為要讓面積變大的,就代表寬或長得比原來的大,但是因為我們從左右兩側開始內縮,我們勢必要找比較高的值,所以才會固定比較高的那側,內縮矮的那側,看能不能找到更高的值。
  • 至於height[left] == height[right]會兩側都內縮是因為兩邊如果都一樣長,那接下來不論是縮哪側,如果遇到比較高的值,還是會因為要選矮的那側,而選到原來的值;如果遇到比較低的值,也會因為要選矮的那側,而高度變低,所以乾脆就兩側一起內縮。

Code

Python

Brute force (Submit Failed)
class Solution:
    def maxArea(self, height: List[int]) -> int:
        x = 0
        y = 0
        max_contain = 0
        
        for index1 in range(len(height)-1):
            y = 0
            for index2 in range(len(height)-1, 0, -1):
                if y >= min(height[index1], height[index2]):
                    continue
                else:
                    y = min(height[index1], height[index2])
                    if max_contain <= (index2-index1)*y:
                        max_contain = (index2-index1)*y
        return max_contain    
Revised
class Solution:
    def maxArea(self, height: List[int]) -> int:
        left = 0
        right = len(height)-1
        
        max_contain = 0
        
        while(left < right):
            max_contain = max(max_contain, min(height[left], height[right])*(right-left) )
            
            if height[left] > height[right]:
                right -= 1
            elif height[left] < height[right]:
                left += 1
            else:
                right -= 1
                left += 1

        return max_contain

C

int maxArea(int* height, int heightSize){
    int left = 0;
    int right = heightSize-1;
    int current_contain = 0;
    int max_contain = 0;

    while(left < right){
        current_contain = (height[left] >= height[right]? height[right]:height[left])*(right-left);
        max_contain = (max_contain >= current_contain? max_contain:current_contain);
        if (height[left] > height[right]){
            right -= 1;
        } else if (height[left] < height[right]){
            left += 1;
        } else {
            right -= 1;
            left += 1;
        }  
    }
        
    return max_contain;
}

Result

  • Python

  • C

大家明天見/images/emoticon/emoticon29.gif


上一篇
Day 8 - Plus One
下一篇
Day 10 - Valid Sudoku
系列文
30天 Leetcode解題之路30

尚未有邦友留言

立即登入留言