配列の最大と最小
配列の最大と最小
このレッスンで分かること
- 計算量はオーダーだけでなく 定数倍 も大事
- 配列から最大値と最小値を求めるのは、計算量の感覚を養う格好の題材です
- 初期化のテクニックがコツです
配列の最大と最小 とは
配列の最大値と最小値を 1 回のスキャンで求める。O(n) で全要素を見る典型例。本レッスンでは、配列の最大と最小 の基本から実際の使いどころまでを整理し、現場で迷わず使える形に落とし込みます。
配列から最大値と最小値を求めるのは、計算量の感覚を養う格好の題材です。max(arr) と min(arr) を別々に呼べばよさそうに見えますが、それぞれが配列を全走査するため、比較回数は約 2n になります。1 回のループで両方同時に求めれば、配列を 2 回走査する無駄が省け、コードもまとまります。ただし比較回数自体は素朴な実装だと約 2n のままです。さらにペア比較を使えば約 1.5n に減らせます。Big-O で見るとどちらも O(n) ですが、定数倍の差は実装の質に直結します。
本レッスンでは「配列の最大値と最小値を 1 回のスキャンで求め、[min, max] の配列で返す」関数を作ります。
計算量はオーダーだけでなく 定数倍 も大事。1 回のループで済むなら 2 回まわす実装より明確に良い。
戦略
初期化のテクニックがコツです。最大値と最小値の変数を arr[0] で初期化し、i = 1 から最後まで比較します。こうすることで、空でない配列なら必ず正しい結果が返ります。
Python での実装例
Python
def minMax(arr):
mn = arr[0]
mx = arr[0]
for i in range(1, len(arr)):
if arr[i] < mn:
mn = arr[i]
if arr[i] > mx:
mx = arr[i]
return [mn, mx]このコードでは、1 回のループで比較を 2 回ずつ行い、合計 2(n-1) 回 の比較で min と max の両方を求められます。min(arr) と max(arr) を別々に呼ぶと 2n 回 弱なので、ほぼ同等ですが、変数が散らばらず読みやすいというメリットがあります。
JavaScript での実装例
JavaScript
function minMax(arr) {
let mn = arr[0];
let mx = arr[0];
for (let i = 1; i < arr.length; i++) {
if (arr[i] < mn) mn = arr[i];
if (arr[i] > mx) mx = arr[i];
}
return [mn, mx];
}組み込みの Math.min(...arr) や Math.max(...arr) を使えば 1 行ですが、ここでは原理を理解するため自前で書きます。
計算量
比較回数は 2(n-1) 回、メモリ使用は変数 2 つ分のみで定数。よって 時間計算量 O(n) 、空間計算量 O(1) です。これは「配列を 1 回スキャンする」典型的なパターンで、計算量の見積もりの基準として覚えておきましょう。
配列を 1 回見るアルゴリズムは
O(n)。ループの中でループするならO(n^2)。これは計算量見積もりの基本ルール。
よくある間違い
1 つ目は 初期値を 0 にしてしまう こと。mn = 0 、mx = 0 で始めると、すべての要素が正のとき mn = 0 のままになってしまいます。arr[0] で初期化するのが安全です。
2 つ目は 空配列を考慮しない こと。arr が空なら arr[0] で IndexError (Python) や undefined (JS) を踏みます。本問では空配列は来ない前提で良いですが、本番コードでは早期 return で対応します。
3 つ目は 戻り値の順番を間違える こと。[mn, mx] の順で返すと仕様で決まっているなら、[mx, mn] で返すとテストが落ちます。順序は仕様書をよく読んで合わせましょう。
やってみよう
[3, 1, 4, 1, 5, 9, 2, 6]で[1, 9]が返ることを確認する。- 単一要素の配列
[42]を渡すと[42, 42]が返る。 - 負数を含む
[-5, -10, -3]で[-10, -3]が返ることを確認する。
「1 回のスキャンで
O(n)」のパターンは、合計・平均・最大連続部分列など、多くの問題で再利用される強力な道具。
Go での実装
Go
func minMax(arr []int) []int {
mn := arr[0]
mx := arr[0]
for i := 1; i < len(arr); i++ {
if arr[i] < mn {
mn = arr[i]
}
if arr[i] > mx {
mx = arr[i]
}
}
return []int{mn, mx}
}比較回数を更に減らせるか
じつは「2 要素ずつペアにして比較する」テクニックで、比較回数を 約 1.5n 回 に減らせます。隣り合う 2 つを先に比較し、小さい方を mn 候補、大きい方を mx 候補とすれば、各ペアあたり比較 3 回 (ペア内 + 2 つの候補) で済みます。素朴な方法は 2n 回、ペア法は 1.5n 回。オーダーは同じ O(n) ですが、定数倍を改善するアルゴリズム設計の好例です。
「定数倍を 25 % 縮める」工夫は、ホットパス (頻繁に呼ばれる関数) では効いてくる。普通のコードでは可読性を優先するのが正解。
再帰的アプローチ (分割統治)
配列を半分に分けて、それぞれの最小・最大を求めて統合するという分割統治のアプローチも考えられます。これは計算量は同じ O(n) ですが、再帰の練習として面白い課題です。第6章で再帰を扱うときに、この問題を再訪してみると、線形スキャンと再帰の違いがクリアに見えるでしょう。
実務での応用
ダッシュボードで「直近 24 時間の最大値と最小値を表示」したい、というよくある要件にこの関数がそのまま使えます。データが大量で O(n) でも遅いなら、データを 時間ウィンドウ で区切り、各ウィンドウの min/max を事前計算しておく セグメント木 や スライディング最小値 のような発展テクニックが必要になります。
よくある質問
Q. このトピックを覚える意味は何ですか？
A. 組み込みの min / max に頼るだけでなく、自前で書いて「1スキャンで何回比較が起きるか」を把握しておくと、ホットパスの計算量を肌感覚で見積もれるようになります。実務での問題解決スピードが格段に上がります。
Q. 実務でこの知識を使う場面は？
A. API の Content-Length 計算、ファイルアップロードのサイズ制限、画像処理での色深度計算など、低レベルな数値を扱う場面で頻出します。OS・ネットワーク・暗号の理解にも繋がるため、CS の共通言語と思って習得しておくと一生使える知識です。
Q. 他の章とどう繋がりますか？
A. 後続の章で扱うデータ構造（スタック・キュー）、アルゴリズム（探索・ソート）の基礎になります。「データを 32 bit でどう表現するか」「メモリにどう載せるか」が分かると、後続トピックの実装が腹落ちしやすくなります。
次のレッスン
次は 累積和で範囲合計 に進みましょう。
事前確認 — 進む前に次の 3 つができることを確認しましょう。
- 最大・最小 の要点を自分の言葉で説明できる
- このレッスンの最小コード (または操作手順) を見ずに書ける
- 練習問題やクイズで間違えた箇所を読み直して理解した
理解度チェック (30 秒)
Q. 最大・最小 とは何か、1 文で説明してください。
A. 本文の「このレッスンで分かること」または冒頭の説明文を見直し、自分の言葉で要約できれば OK。詰まったら本レッスンの最初の H2 セクションを読み返してみましょう。
関連レッスン
要件
- 1 回のループで最小値と最大値の両方を求めること
- 組み込みの min() / max() / Math.min / Math.max は使わない
- 戻り値は [min, max] の順の長さ 2 の配列
入出力例
test-cases.txt
minMax([3,1,4,1,5,9,2,6]) → [1,9]
minMax([42]) → [42,42]
minMax([7,7,7]) → [7,7]
minMax([-5,-10,-3]) → [-10,-3]
minMax([1,2,3,4,5]) → [1,5]
minMax([5,4,3,2,1]) → [1,5]