Leetcode 2718. Sum of Matrix After Queries

[Woodyiiiiiii]

2718. Sum of Matrix After Queries

2718. Sum of Matrix After Queries

这道题作为WC 348的Q3，我没做出啦，太失败了...

首先，看到时间复杂度，想到大概率用不了二分，那就只能用一些缓存的思想，在O(n)内完成。那该存什么呢？考虑到行和列两种角度，可以从每一步影响的行/列思考。

接着关键是倒序，因为题目里是覆写，说明后面的操作才是最后的结果。

复写操作要用倒序，多思考倒序。

class Solution {
    public long matrixSumQueries(int n, int[][] queries) {
        int rowCnt = 0, colCnt = 0;
        long[] rows = new long[n], cols = new long[n];
        Arrays.fill(rows, -1);
        Arrays.fill(cols, -1);
        long ans = 0;
        for (int i = queries.length - 1; i >= 0; i--) {
            int[] query = queries[i];
            int type = query[0], idx = query[1];
            long val = query[2];
            if (type == 0) {
                if (rows[idx] == -1) {
                    rows[idx] = val;
                    rowCnt++;
                    ans += (val * (n - colCnt));
                } else {
                    continue;
                }
            } else if (type == 1) {
                if (cols[idx] == -1) {
                    cols[idx] = val;
                    colCnt++;
                    ans += (val * (n - rowCnt));
                } else {
                    continue;
                }
            }
            System.out.println(ans);
        }
        return ans;
    }
}