对角线遍历

对于遍历一个矩阵（m x n）的所有对角线，这里指的是从左上到右下的对角线，除了常规的遍历方式，还有一种更加简洁的方式

理论

对于每一条对角线，可以知道其中的 i - j 是一个固定的值。

可以设 k = i - j + n，每一条对角线都对应了一个 k ，最右上对角线(i = 0，j = n - 1)对应的 k 是 1

最左下对角线(i = m - 1, j = 0)对应的 k 是 m + n - 1，可以得到 k 的取值范围是 (1, m + n - 1)

对角线都是从上向下遍历的也就是 i 会变大，反推公式可以得到 i = k + j - n，j = i - k + n，也就是当i，j的变化是成正比的。当 i 取最小 0，j 取最小 n - k，当 i 取最大 m - 1，j 取最大 m + n - k - 1

当然，不是每条对角线 i 的取值范围都是 (0, m - 1)，对于一条对角线，如果 i 超出了其对应的范围，那么 j一定也会越界，所以，可以用 j 的范围来反向限制 i，对于一个矩阵来说，j 的范围是 (0, n - 1)

对于一条对角线来说，j 的范围是 (n - k, m + n - k - 1)，两者取并集，可以得到 j 的取值范围是

（max(0, n - k), min(n - 1, m + n - k - 1)）

遍历的条件是 (minj，maxj)，使用 j 推出 i，就可以从上到下的遍历对角线了，同时 k 从 1 -> m + n - 1，就可以从左上到右下的遍历所有对角线。

案例

public int[][] differenceOfDistinctValues(int[][] grid) {
    int m = grid.length;
    int n = grid[0].length;
    // k = i - j + n, k 的 取值范围为 (1, m + n - 1)
    for (int k = 1; k <= m + n - 1; k++) {
        // j = i - k + n 
        int minJ = Math.max(0, n - k); // i = 0
        int maxJ = Math.min(n - 1, m + n - k - 1); // i = m - 1;
        long set = 0;
        for (int j = minJ; j <= maxJ; j++) {
            // i = k + j - n;
            int i = k + j - n;
            ...
        }

        set = 0;
        for (int j = maxJ; j >= minJ; j--) {
            int i = k + j - n;
...
        }
    }
    return ans;
}

使用long代替hashset

理论

long在Java中使用了8个字节，对于一些数值范围小于64，或者情况数不超过64种的案例中，可以使用一个long中的某个位来标识是否存在。

案例

long set = 0;
for (int j = minJ; j <= maxJ; j++) {
    // i = k + j - n;
    int i = k + j - n;
    ans[i][j] = Long.bitCount(set);
    set |= 1L << grid[i][j];
}

set = 0;
for (int j = maxJ; j >= minJ; j--) {
    int i = k + j - n;
    ans[i][j] = Math.abs(ans[i][j] - Long.bitCount(set));
    set |= 1L << grid[i][j];
}

这里的 grid[i][j]的取值范围是 [0, 50]，使用long来记录grid[i][j]是否出现可以优化掉Set

注意set的赋值操作是 set |= 1L << grid[i][j]

处理有效括号字符串的通用思路

在有效括号字符串的任意一个前缀中，左括号的数量都大于等于右括号的数量。因为对于有效括号字符串的前缀来说，每个右括号的左边，必然有与之匹配的左括号，但是左括号不一定有与之匹配的右括号。

根据这一性质，从左到右遍历字符串 s，统计未匹配的左括号个数c；遇到左括号就把c加一，遇到右括号就把c减一(匹配一个左括号)。如果遇到任何时刻c都不为负数，且最终c = 0，那么 s 就是有效括号字符串。