LeetCode 1732. Find the Highest Altitude - 空間計算量をO(1)とするための変数利用

1732. Find the Highest Altitude

https://leetcode.com/problems/find-the-highest-altitude/description

Intution

• 自転車で旅をする際に、標高の変化を記録したデータから、最も高い地点（最高標高）をどうやって見つけるか？
  • 標高差を保存する配列を定義してループごとに前の地点の標高 + 次の地点への変化量で計算。最後にmaxを算出する。

ruby

def largest_aaltitude(gain)
  diff = [0]
  gain.each.with_index do |g, index|
    diff << g + diff[index]
  end
  diff.max
end

Approach

python

• すべての標高差を配列に格納する
  • gain配列のサイズが大きい場合、それに比例して新しい配列のためのメモリが必要になります。これは空間計算量（Space Complexity）の観点から非効率的

class Solution:
    def largestAltitude(self, gain: List[int]) -> int:
        diff = [0]

        for i in range(len(gain)):
            diff.append(gain[i] + diff[i])
        
        return max(diff)

• 2つの変数で最高標高を保持する
  • gain配列のサイズに関わらず、必要なメモリは一定です。

class Solution:
    def largestAltitude(self, gain: List[int]) -> int:
        highestPoint = 0
        currentPoint = 0

        for altitude_gain in gain:
            currentPoint += altitude_gain
            highestPoint = max(highestPoint, currentPoint)
        
        return highestPoint

typescript

function largestAltitude(gain: number[]): number {
    let higestPoint: number = 0
    let currentPoint: number = 0

    for (const g of gain) {
        currentPoint += g
        higestPoint = Math.max(higestPoint, currentPoint)
    }
    return higestPoint
};

• for...ofがArray以外にも適用できる汎用的なループ構文

特徴	forEach	for...of
構文	メソッド	ループ構文(ES6で導入)
ループ制御	break, continue, return で中断 不可	break, continue, return で中断 可能
適用範囲	Array のみ	Iterable オブジェクト全般
性能	わずかに遅い（コールバックのオーバーヘッド）	わずかに速い

golang

• for...rangeを使ってすべての要素を処理する。

func largestAltitude(gain []int) int {
    var highestPoint int = 0
    var currentPoint int = 0

    for _, g := range gain {
        currentPoint += g
        highestPoint = max(highestPoint, currentPoint)
    } 
    return highestPoint
}

学習のポイント

• 空間計算量を意識してコーディングする。メモリ消費量を一定にするには既存の配列nのコピーを作るのではなく、特定用途の変数を定義すると良い。
• forEachはArrayにしか適用できないメソッドのため、for...ofのほうがArray以外にも適用できる汎用的なループ構文のため利用するとよい。