破題

這題要求我們模擬一系列的方塊從天空掉落到一維的數線上，並且回傳每次掉落後最高的高度。

跟一流的人才幹大事，享受成功進步的高級樂趣！
內推機會來啦！能與優秀的程式設計師共事，是特別痛快的事，因為厲害的工程師大神會刺激你想要迎頭趕上的上進心，尤其是一起討論解決方案時，他們會觸發你有更好的解決思維能力，彼此共同成長並且一起享受解謎與破關般的樂趣。 你一定聽得懂我在說甚麼感覺，趕快把握機會，動動手指投遞履歷吧！ 立即加入「面試讀書會」，和大家一起準備面試！

內推機會	加入讀書會 (邀請碼：6942)

解題思路

這個演算法的思路是使用一個整數陣列 qans 來記錄每個方塊的高度，並且遍歷所有的方塊位置。對於每個方塊，我們首先計算它的左右邊界，然後將它的邊長加到 qans 中。接著，我們檢查它之後的所有方塊，如果有重疊，就將 qans 更新為目前方塊和重疊方塊中較大的高度。最後，我們用一個變數 maxHeight 來記錄目前最高的高度，並且將它加入到答案陣列 ans 中。

程式

import java.lang.Integer.max

class Solution {
    fun fallingSquares(positions: Array<IntArray>): List<Int> {
        val qans = IntArray(positions.size)
        positions.forEachIndexed { index, position ->
            val left = position[0]
            val sideLength = position[1]
            val right = left + sideLength
            qans[index] += sideLength

            for (i in index + 1 until positions.size) {
                val left2 = positions[i][0]
                val sideLength2 = positions[i][1]
                val right2 = left2 + sideLength2
                if (left < right2 && right > left2) {
                    qans[i] = max(qans[index], qans[i])
                }
            }
        }

        val ans = mutableListOf<Int>()
        var maxHeight = 0
        qans.forEach {
            maxHeight = max(maxHeight, it)
            ans.add(maxHeight)
        }

        return ans
    }
}

複雜度分析

• 時間複雜度:
  ，其中 是方塊的數量。我們需要遍歷所有的方塊，並且對於每個方塊，我們還需要檢查它之後的所有方塊是否有重疊。

• 空間複雜度:
  ，其中 是方塊的數量。我們需要使用一個陣列 qans 來記錄每個方塊的高度，以及一個陣列 ans 來存儲答案。

　更多 LeetCode 解答在此，一起來學習！

內推機會來啦！

跟一流的人才幹大事，享受成功進步的高級樂趣！

內推機會	加入讀書會 (邀請碼：6942)