iT邦幫忙

2021 iThome 鐵人賽

DAY 13
0
AI & Data

想到甚麼打甚麼系列 第 13

找LeetCode上簡單的題目來撐過30天啦(DAY13)

題號:11 標題:Container With Most Water 難度:Medium

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 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

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

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

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

我的程式碼

int maxArea(int* height, int heightSize){
    int area=0,area_temp;
    int r,l,temp;
    l=0; r=heightSize-1;
    while(r>l){

        printf("%d,%d\n",r,l);
        if(height[r]>height[l]){
            area_temp =  height[l] * (r-l);
            temp = height[r];
            l++;
            while(temp> height[l]){
                if(r>l){
                    break;
                }
                l++;
            }
        }else{
            area_temp =  height[r] * (r-l); 
            temp = height[l];
            r--;
            while(temp> height[r]){
                if(r>l){
                    break;
                }
                r--;
            }
        }
        
        if(area_temp>area){
            area = area_temp;
        } 
    }
    
    return area;
}

DAY13心得
昨天要感謝台積電辣妹,今天要感謝男友給我解題提示,不然我一直超時,寫到現在覺得最難的還是特殊CASE跟時間複雜度,然後我真的要去睡了


上一篇
找LeetCode上簡單的題目來撐過30天啦(DAY12)
下一篇
找LeetCode上簡單的題目來撐過30天啦(DAY14)
系列文
想到甚麼打甚麼30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言