刷刷刷LeetCode(二) : 時間複雜度

突然發現，LeetCode中級難度有兩種，一種是單純Easy的難度加強版，另一種則是要求時間複雜度，以下是一題簡單，但要做到好十分困難:

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 line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Note: You may not slant the container and n is at least 2.

Example:
Input: [1,8,6,2,5,4,8,3,7]
Output: 49

簡單來說，要找出一串陣列所能圍出的最大矩陣(如上圖 底*較低的高)

直覺上來看，恩~~用暴力解法吧!直接兩個for :

class Solution {
    public int maxArea(int[] height) {
        int MAX = 0;
        for(int i=0;i<height.length;i++){
            for(int j=i;j<height.length;j++){
                int shorter = compare(height[i],height[j]);
                int temp = shorter * (j-i);
                if(temp > MAX){
                    MAX = temp;
                }
            }
        }
        return MAX;
    }
    
    public int compare(int a,int b){   //比較大小，回傳小
        return a>b?b:a;
    }
}

恩~~開心的通過了，這題真簡單，結果出來一看 ??? 居然慘不忍睹，被80%的網友屌打速度。跟時間軸左側的高樓相比，我們根本在平民窟。

這可不行，我們的時間複雜度為O(N2)，其他80%的網友肯定有方法將時間複雜度降低到O(N) 。

由於腦袋不靈光，我想了半小時後放棄了，偷偷看其他人是怎麼寫的:

每次都從最左邊開始時間當然耗的多啊 ，為什麼不從中間開始?

— by 極客學院

因此有了新的寫法 (我是從左右兩邊開始啦):

class Solution {
    public int maxArea(int[] height) {
        int MAX = 0;
        int left = 0;
        int right = height.length -1;
        while(left <right){
            int shorter = compare(height[left],height[right]);
            int temp = shorter * (right-left);
            if(temp >MAX){
                MAX = temp;
            }
            if(shorter == height[left]){ 
            //如果左半段較短，尋找左邊更長的可能
                left++;
            }else{
                right--;
            }
        }
        return MAX;
    }
    
    public int compare(int a,int b){
        return a>b?b:a;
    }
}

思想是我們保存兩邊高最長的那一段，捨棄較短的那一段去找找有沒有更長的一段。時間複雜度為O(N)，果不其然，這樣寫後就能打敗68%的網友了!!終於能來到富豪區了!!

參考資料

極客學院: http://wiki.jikexueyuan.com/project/leetcode-book/10.html