行列
01 / 共通の仕組み
行列は単なる線形列ではなく、2 次元の座標空間 — 各セルは2 つの添字で指定され、 その組み合わせ方が問題ごとに異なる。要は正しい「歩き方」を見つけること。 3 つの古典的なサブパターン:その場回転(転置 + 行反転)、螺旋走査(4 つの境界が内側に収縮)、階段探索(片方向は単調増加、もう片方向は単調減少となる角から開始)。
01 / 一文での本質
4 つの境界 —— 上・右・下・左 —— を保持し、それらが囲む矩形の外周を歩く。 各方向の 1 辺を歩き終えるごとに、その境界を内側へ 1 だけ縮める。 境界が交差するまで、層を 1 枚ずつ剥がしていく。
問題M の要素を螺旋順に返すM1 2 3 ; 4 5 6 ; 7 8 9
グリッドは 3 × 3。初期境界は top=0, bottom=2, left=0, right=2。外周を歩き、縮め、繰り返す。
ステップ
0 / 15
現在
—
訪問数
0 / 9
0 / 15
02 / パターンの骨格
# 未訪問矩形を囲む 4 つの境界top ← 0; bottom ← R-1left ← 0; right ← C-1while top ≤ bottom and left ≤ right:# 1) top 行を左から右へfor c in left..right: visit(top, c)top ← top + 1# 2) right 列を上から下へfor r in top..bottom: visit(r, right)right ← right − 1if top ≤ bottom:# 3) bottom 行を右から左へfor c in right..left: visit(bottom, c)bottom ← bottom − 1if left ≤ right:# 4) left 列を下から上へfor r in bottom..top: visit(r, left)left ← left + 1
03 / このパターンを使うべき合図
「螺旋順走査」
LC 54。最も典型的な用途 —— 各セルを螺旋順に出力する。4 つの境界 + 4 方向 + 走破後に縮める。
O(R · C)、各セルはちょうど 1 回訪問。「螺旋順に行列を埋める」
LC 59。同じ歩き方の逆向き利用 —— 値を読む代わりに
1, 2, 3, …, n² を順に書き込む。境界の骨組みは同じで、訪問ステップが読みから書きに変わるだけ。「層ごとの回転 / 層ごとの処理」
同心リング に自然に分解できる問題 —— 各リングをその場で回転、層ごとの画像フィルタ、 外周の集計など。4 境界フレームは「1 層の反復」そのもの。外側に層ループを 1 つ巻けばよい。
「行列の外周問題」
矩形(あるいは部分矩形)の境界上のセルを問う問題では、螺旋走査が一度で全て返してくれる。 外周和、リング上の問い合わせ、螺旋座標パズル(LC 885、LC 2326)などに有効。
04 / よくある落とし穴
i.
3 番目・4 番目の走査前の条件チェックを忘れる。
残るのが 1 行または 1 列のみのとき、3 番目の走査(bottom 行を右→左)は最初の走査で消費済みの行を 再訪してしまう。4 番目も同様に列を重複する。3 番目は
top ≤ bottom で、 4 番目は left ≤ right でガードする。これを怠ると非正方形の入力で重複出力になる。ii.
境界更新のオフバイワン。
各境界は対応する走査の後に進める —— L→R 走査の後で
top++、 T→B 走査の後で right−−、以下同様。top++ を間違った位置 (走査の前 / 別の境界)に置くと、矩形が潰れて 1 行抜けたり同じ行を二度歩いたりする。iii.
4 本のほぼ重複した index ループを書く(歩行ポインタにすべき)。
より綺麗な書き方:
(r, c) と方向インデックス d ∈ {0,1,2,3} を保持し、dr/dc 配列を使う。1 歩進めて、もし現在の境界の外に出るなら d ← (d + 1) % 4 として、直前に離れた境界を縮める。ループは 1 本、終了条件も 1 つ —— ほぼ同じ for を 4 本書くより、間違える場所が遥かに少ない。05 / LeetCode で練習
螺旋走査に関する 4 問。最初の 2 問は直接利用 —— 読み vs. 書き。 残り 2 問は任意の開始点や連結リスト出力への一般化。
— / どれをいつ使うか
その場回転
グリッド自体の幾何変換 — 90° / 180° 回転、転置、鏡像 — を行う問題で使う。 2 段(転置 + 行反転)に分解すれば追加グリッド無しでその場処理できる。
転置 + 反転 · LC 48
螺旋走査
縮小していく矩形の外周沿いに全セルを訪問する必要があるとき — 螺旋出力、螺旋充填、層カウント。 4 つの境界を保持し、1 周ごとに内側へ収縮させる。
4 つの境界 · LC 54 · LC 59
階段探索
行と列の両方向で単調な行列で、値を探すときに使う。 片方向が厳密に増加、もう片方向が厳密に減少する角から始めれば、 1 回の比較で 1 行または 1 列を丸ごと除外できる。
右上角から · LC 240 · O(N + M)