LeetCode запись решения 2536. Увеличение подматриц на единицу

Увеличение подматриц на единицу - LeetCode

Вопрос

Учитывая число n, представляющее двумерную матрицу длины и ширины n, со всеми начальными значениями 0, и двумерный массив запросов, queries[i] = {r1, c1, r2, c2}, представляющих все координаты в столбцах r1 - r2, строках c1 - c2, все плюс 1, вернуть двумерную матрицу после выполнения запросов

Условия

• 1 ≤ n ≤ 500
• 1 ≤ длина запросов ≤ 10⁴

Смотрите

• Если каждый элемент в каждом запросе заполняется в соответствии с диапазоном, это интуитивно понятно, но TLE, худший случай - O(n²*m) m = длина запроса
• Мы можем использовать подход префиксной суммы для записи только приращения значения в каждой строке, например, {r1,c1,r2,c2} прибавить 1 к c1 в каждом столбце от r1 до r2, затем вычесть 1 из c2+1, и, наконец, вычислить префиксную сумму для каждой строки

Решение (префиксная сумма)

class Solution {
    public int[][] rangeAddQueries(int n, int[][] queries) {
        int ans [][] = new int [n][n];
        for(int[] q:queries) {
            for(int r=q[0];r<=q[2];r++) {
                ans[r][q[1]] ++;
                // 注意邊界
                if (q[3]+1 < n)
                    ans[r][q[3]+1] --;
            }
        }
        for(int r=0;r<n;r++)
            for(int c=1;c<n;c++) 
                ans[r][c] += ans[r][c-1];
        return ans;
    }
}

Результат

TC: O(n*m)

SC: O(n*n)