数组
如何对角线遍历数组？
https://leetcode.cn/problems/difference-of-number-of-distinct-values-on-diagonals/description/
- 暴力
for循环遍历，每遍历一个数，计算它所在对角线，需要遍历很多遍对角线
以下为个人写的暴力代码
class Solution {
public int[][] differenceOfDistinctValues(int[][] grid) {
int row = grid.length;
int col = grid[0].length;
int[][] res = new int[row][col];
for(int i = 0;i<row;i++){
for(int j = 0;j<col;j++){
int temi = i+1;
int temj = j+1;
Set<Integer> set1 = new HashSet<>();
while(temi < row && temj < col){
set1.add(grid[temi][temj]);
temi++;
temj++;
}
temi = i-1;
temj = j-1;
Set<Integer> set2 = new HashSet<>();
while(temi >= 0 && temj >= 0){
set2.add(grid[temi][temj]);
temi--;
temj--;
}
res[i][j] = Math.abs(set1.size() - set2.size());
}
}
return res;
}
}- 前后缀分解
对于同一条对角线，方法一会多次遍历。比如计算 ans[0][0] 的时候我们会遍历主对角线，计算 ans[1][1] 的时候我们又会遍历主对角线。怎么减少遍历次数？
我们按从右上到左下的对角线来遍历，可以发现在同一条对角线上，j - i 为一个固定值即 j - i = c
当我们按从右上到左下的对角线来遍历时，我们令右上角的对角线为第k条，k = n - (j - i)，就可以得出k的范围为[1,n+m - 1]（n为列数，m为行数），所有我们遍历k就是在从右上到左下来遍历对角线，那如何得到对角线上的点的坐标呢？不要忘记** j - i = c 是常数**，由k = n - (j - i) 可以得出 j = n - k + i ，i 属于 [0,m-1]。
所以
- 当 i=0 的时候 j 取到最小值 n−k，但这个数不能是负数，所以最小的 j 是 max(n−k,0)。
- 当 i=m−1 的时候 j 取到最大值 m+n−1−k，但这个数不能超过 n−1，所以最大的 j 是 min(m+n−1−k,n−1)。
当得到 j 的范围后，就可以遍历 j 了，在遍历每个 j 时，我们可以算出对应的 i 的值，并且这个遍历是沿着对角线进行的。
下述为灵神的代码
class Solution {
public int[][] differenceOfDistinctValues(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
int[][] ans = new int[m][n];
Set<Integer> set = new HashSet<>();
// 第一排在右上，最后一排在左下
// 每排从左上到右下
// 令 k=i-j+n，那么右上角 k=1，左下角 k=m+n-1
for (int k = 1; k < m + n; k++) {
// 核心：计算 j 的最小值和最大值
int minJ = Math.max(n - k, 0); // i=0 的时候，j=n-k，但不能是负数
int maxJ = Math.min(m + n - 1 - k, n - 1); // i=m-1 的时候，j=m+n-1-k，但不能超过 n-1
set.clear();
for (int j = minJ; j <= maxJ; j++) {
int i = k + j - n;
ans[i][j] = set.size(); // topLeft[i][j] == set.size()
set.add(grid[i][j]);
}
set.clear();
for (int j = maxJ; j >= minJ; j--) {
int i = k + j - n;
ans[i][j] = Math.abs(ans[i][j] - set.size()); // bottomRight[i][j] == set.size()
set.add(grid[i][j]);
}
}
return ans;
}
}有序三元组的最大值I
2873. 有序三元组中的最大值 I - 力扣（LeetCode）
一. 直接暴力
三层for循环暴力求解
**注意：**一定要预防整型溢出的的情况（踩坑）
class Solution {
public long maximumTripletValue(int[] nums) {
long res = 0;
int len = nums.length;
for(int i = 0; i < len;i++){
for(int j = i+1; j < len;j++){
for(int k = j + 1; k < len;k++){
long temp = (nums[i] - nums[j]) * nums[k] * 1l;
res = res > temp ? res:temp;
}
}
}
return res;
}
}long temp = (nums[i] - nums[j]) * nums[k] * 1l;
上述这句代码看似进行了类型转化，但其实是无效转化
原因：(nums[i] - nums[j])算出来的是一个整型，所以(nums[i] - nums[j]) * nums[k]算出来的也是一个整型，如果数字很大的话，在这一步就已经溢出了，在将其 * 1l 只是将溢出后的值进行转化，无效！！！！
GPT解释：
** 这里
**(nums[i] - nums[j]) * nums[k]**先进行运算，然后再乘以**1l**。
****由于**nums[i] - nums[j]**和**nums[k]**都是**int**类型，**(nums[i] - nums[j]) * nums[k]**的计算仍然是**int**类型。如果结果超出了**int**的范围（即大于**2^31-1**或小于**-2^31**），会发生 整数溢出，然后再将溢出的**int**转换为**long**，但溢出的信息已经丢失了，导致结果错误。 **
class Solution {
public long maximumTripletValue(int[] nums) {
long res = 0;
int len = nums.length;
for(int i = 0; i < len;i++){
for(int j = i+1; j < len;j++){
for(int k = j + 1; k < len;k++){
long temp = 1l * (nums[i] - nums[j]) * nums[k];
res = res > temp ? res:temp;
}
}
}
return res;
}
}上述代码中，我们在(nums[i] - nums[j]) 后就将其转化为long类型，所以后面进行(nums[i] - nums[j]) * nums[k] 算出来的还是long类型，这里其实也有溢出风险，因为当nums[i]很大时(nums[i] - nums[j])直接就溢出了，但在这不可能，因为nums是一个整型数组
GPT解释
由于
1l是long类型，**1l * (nums[i] - nums[j])**** 立即提升为**long**类型**，因此整个计算过程都是long类型，不会发生int溢出。
总结
- 第一段代码可能发生
**int**溢出，因为(nums[i] - nums[j]) * nums[k]仍然是int运算，只有最后才转换为long。 - 第二段代码避免了溢出，因为
1l * (nums[i] - nums[j])让整个计算在long里进行。
二. 贪心
我们固定 k，那么当 nums[i]−nums[j] 取最大值时，三元组的值最大。我们可以用 imax 维护 nums[i] 的最大值，dmax 维护 nums[i]−nums[j] 的最大值，在枚举 k 的过程中，更新 dmax 和 imax。
class Solution {
public long maximumTripletValue(int[] nums) {
long res = 0;
int len = nums.length;
int imax = 0;
int detaMax = 0;
for(int i = 0; i < len;i++){
res = Math.max(res,(long)detaMax*nums[i]);
detaMax = Math.max(detaMax,imax-nums[i]);
imax = Math.max(imax,nums[i]);
}
return res;
}
}