1476. LeetCodeのサブレクタングルクエリ - 🔥シンプルな論理的なJavaソリューション - 66%より速い

与えられた長方形のサブレクタングルを更新し、問い合わせることができるクラスを実装する問題です。サブレクタングルは4つの角（row1, col1, row2, col2）で定義されます。この問題を解決する一つの方法は、元の長方形とクラス内の更新のリストを保存することです。各更新にはサブレクタングルの座標とそれを埋めるための新しい値が含まれます。特定の位置（row, col）で値を問い合わせるためには、逆順で更新を通じて繰り返しチェックし、位置がどのサブレクタングルにでも当てはまるかどうかを確かめます。当てはまれば、対応する値を返します。そうでなければ、長方形から元の値を返します。

このアプローチを実装するために、元の長方形を保存する2D配列と更新を保存するリストの2つのデータ構造が必要です。コンストラクタは長方形を入力として受け取り、配列とリストを初期化します。updateSubrectangleメソッドは与えられたパラメータでリストに新しい更新を追加します。getValueメソッドはリストを最後から繰り返し、与えられた位置がどの更新にも含まれるかチェックします。もしそうなら、その更新から値を返します。そうでなければ、配列から値を返します。

• 時間複雑度：
  コンストラクタの時間複雑度は

  O(mn)
  で、ここで
  m
  と
  n
  はそれぞれ長方形の行数と列数です。updateSubrectangleメソッドの時間複雑度は
  O(1)
  で、リストに追加するだけです。getValueメソッドの時間複雑度は
  O(k)
  で、ここで
  k
  はリストにある更新の数です。

• 空間複雑度：
  クラスの空間複雑度は

  O(mn + k)
  で、ここで
  m
  、
  n
  、そして
  k
  は上述のように定義されます。配列を保存するために
  O(mn)
  のスペースが必要で、リストを保存するために
  O(k)
  のスペースが必要です。

import java.util.*;

class SubrectangleQueries {
 private int[][] rect;
 private List<int[]> updates;

 public SubrectangleQueries(int[][] rectangle) {
 rect = rectangle;
 updates = new ArrayList<>();
 }

 public void updateSubrectangle(int row1, int col1, int row2, int col2, int newValue) {
 updates.add(new int[]{row1, col1, row2, col2, newValue});
 }

 public int getValue(int row, int col) {
 for (int i = updates.size() - 1; i >= 0; i--) {
 int[] update = updates.get(i);
 if (row >= update[0] && row <= update[2] && col >= update[1] && col <= update[3]) {
 return update[4];
 }
 }
 return rect[row][col];
 }
}

私のLeetCodeの解答: https://leetcode.com/VerisimilitudeX/

こちらの記事はdev.toの良い記事を日本人向けに翻訳しています。
https://dev.to/verisimilitudex/1476-leetcodes-subrectangle-queries-simple-logical-java-solution-beats-66-ohb