如何找到畫天際線隨時間和空間複雜== O（N）

Question

我最近花了一個在線編碼測試需要至少招。我獲得了100％的正確性，但0％的表現。我怎麼能寫我的解決方案來獲得更好的性能？我不敢相信我打進0％。

[編碼試驗]

您想油漆使用由配置成一列的矩形建築物的連續水平筆劃天際線。每個水平行程都是一個單位高和任意寬。這些建築都是相同的寬度，但它們可能有不同的高度。天際線形狀以陣列A的形式給出，其元素以連續建築物爲單位指定高度。

例如：

A[0] = 1 
A[1] = 3 
A[2] = 1 
A[3] = 3 
A[4] = 2 
A[5] = 1 

將產生的天際線（要求5筆）：

收件給定一個非空數組A由N個整數的函數，返回最小數繪製由數組表示的天際線所需的水平筆畫。如果筆劃數超過了1,000,000,000，函數應該返回-1。時間複雜度應該是O（N）。空間複雜度應該超出輸入存儲的O（N）（不包括輸入參數所需的存儲空間）。

public static int solution(int[] A) 
{ 
    int largestNumber = 0; 
    for (int i = 0; i < A.Length; i++) 
    { 
     if(A[i] > largestNumber) 
     { 
      largestNumber = A[i]; 
     } 
    } 

    int strokeCount = 0; 
    for (int i = 0; i <= largestNumber; i++) 
    { 
     bool highestMatch = false; 
     for (int j = 0; j < A.Length; j++) 
     { 
      if (!highestMatch && A[j] >= (i + 1)) 
      { 
       strokeCount++; 
       highestMatch = true; 
      } 
      else 
      { 
       if (highestMatch && A[j] < (i + 1)) 
       { 
        highestMatch = false; 
       } 
      } 
     } 
    } 

    if(strokeCount > 1000000000) 
    { 
     return -1; 
    } 
    else 
    { 
     return strokeCount; 
    } 
} 

Answer 1

我們可以此話，如果A[n+1] > A[n]我們不得不開始A[n+1]-A[n]招。但是如果A[n+1] < A[n]我們必須結束A[n]-A[n+1]。

由於我們感興趣的只有開始筆畫的數量，所以當條件A[n+1] > A[n]被滿足時，我們可以求和A[n+1]-A[n]。

這意味着我們做的最多N-1款項，即是O(N)。

class Program 
{ 
    public static int ComputeNumberOfStrokes(List<int> skyline) 
    { 
     const int MAX = 1000000001; 
     var strokes = skyline.Zip(skyline.Skip(1), (a, b) => b - a) 
           .Where(d => d > 0) 
           .Aggregate(skyline[0], (a, b) => Math.Min(a + b, MAX)); 
     return strokes >= MAX ? -1 : strokes; 
    } 

    static void Main(string[] args) 
    { 
     var skyline1 = new List<int> { 1, 3, 1, 3, 2, 1 }; 
     var skyline2 = new List<int> { 1, 2, 3, 4, 3, 2, 1 }; 
     var skyline3 = new List<int> { 1, 2, 3, 4, 1, 2, 3, 4 }; 
     Console.WriteLine(ComputeNumberOfStrokes(skyline1)); 
     Console.WriteLine(ComputeNumberOfStrokes(skyline2)); 
     Console.WriteLine(ComputeNumberOfStrokes(skyline3)); 
     Console.In.ReadLine(); 
    } 
} 

這將返回5 4 7。哪些是預期的結果。

Answer 2

很簡單的解決方案，這樣做具有恆定空間線性時間單通道：

int strokeCount(IEnumerable<int> skyline) 
{ 
    int level = 0; 
    int strokes = 0; 

    foreach (int height in skyline) 
    { 
     // if the building is higher than the current level, we need 
     // to make (level - height) new strokes 
     if (height > level) 
     { 
      strokes += height - level; 
      level = height; 
     } 
     // if the building is lower than the current level, we need 
     // to end the difference in strokes, but this doesn’t cost 
     // 「new」 ones 
     else if (height < level) 
     { 
      level = height; 
     } 
     // if we stay on the same level, don’t do anything 

     // explicitely check for the maximum stroke count for every 
     // building, so we can abort early 
     if (strokes > 1000000000) 
      return -1; 
    } 
    return strokes; 
} 

Answer 3

這裏有一個簡單的解決方案在JavaScript

function solution(A) { 
    var strokesCount = 0; 
    var currStrokeHeight = 0; 

    for (var i = 0; i < A.length; i++) { 
     if (currStrokeHeight < A[i]) { 
      // next building is taller than our current stroke height 
      // add the difference between heights to strokesCount 
      strokesCount += A[i] - currStrokeHeight; 

      // edge case 
      if (strokesCount > 1000000000) { 
      return -1; 
      } 
     } 
     currStrokeHeight = A[i]; 
    } 

    return strokesCount; 
}