LeetCode 1732. Find the Highest Altitude

プログラミング
Page content

どうも、たくチャレ(@takuchalle)です。

LeetCodeの1732. Find the Highest Altitudeを解いてみました。

設問

高さの差分の配列データが与えられるので、一番高い標高を返す問題。

解

現在の標高altitudeと一番高い標高maxAltitudeを保存し、maxAltitudeを返すようにしています。

このように累積和を利用する問題はPrefix Sumと呼ばれます。(解いた後に知りました)

計算量はO(N)で、消費メモリはO(1)です。

class Solution {
   public:
    int largestAltitude(vector<int>& gain) {
        int altitude = 0;
        int maxAltitude = 0;

        for (auto v : gain) {
            altitude += v;
            maxAltitude = max(altitude, maxAltitude);
        }

        return maxAltitude;
    }
};