当前位置：首页 > news >正文

完整教程：【数据结构】算法题

news 2026/4/4 10:14:29

轻松函数/值（直接调用）

写法	功能	举例
INT_MAX、INT_MIN	表示最大、最小的整数	int a=INT _MAX;
max()、min()	两者取大、取小	x=max(a,b); y=min(a,b)l
swap();	将a、b所存的值交换	swap(a,b); swap(&a,&b);
abs();	绝对值函数	a=abs(i-j);

2025

（1）双重循环
应用两个嵌套的for循环遍历数组A的所有可能的(i,j)组合，其中0 $\leq$ i $\leq$ j $\leq$ n-1。对于每个i，遍历所有j $\geq$ i，计算A[i]*A[j]，并记录其中的最大值到res[i]中
void CalMulMax(int A[ ],int res[ ],int n){
for(int i=0;i<n;i++){ //遍历每个起始位置i
int maxMul = A[i]*A[j]; //初始化
for(int j=i;j<n;j++){ //遍历所有j>i
int currentMul = A[i]*A[j];
if(currentMul > maxMul){ //当前乘积更大，更新
maxMul = currentMul;
}
}
res[i] = maxMul; //将最大乘积存入res[i]
}
}
时间复杂度O(n^2)：使用了两个嵌套的for循环
空间复杂度O(1)：使用了常数级别的额外空间

（2）利用辅助数组B和C
预先计算并存储每个位置i到数组末尾n-1之间的最大值B[i]和最小值C[i]
对每个元素A[i]：
假设A[i]为非负数，则最大乘积为A[i]*B[i]
如果A[i]为负数，则最大的乘积为A[i]*C[i]
这样可以子啊一次遍历中预处理B和C，然后在另一次遍历中计算res数组
void CalMulMax(int A[ ],int res[ ],int n){
int B[n]; //B[i]表示A[i..n-1]中的最大值
int C[n]; //C[i]表示A[i..n-1]中的最小值
//从后向前遍历，填充B和C数组
B[n-1]=A[n-1];
C[n-1]=A[n-1];
for(int i=n-2;i>=0;i--){
B[i] = max(B[i+1],A[i]);
C[i] = min(C[i+1],A[i]);
}
//计算res数组，最大值只可能是A[i]*B[i]或A[i]*C[i]
for(int i=0;i<n;i++)
res[i] = max(A[i]*B[i],A[i]*C[i]);
}
时间复杂度O(n)：应为预处理B和C数组各需一次线性遍历，计算res数组也只需一次线性遍历
空间复杂度O(n)：需要额外的两个辅助数组B和C，每个大小为n

（3）使用辅助变量B和C
在（2）的基础上，只需用变量存最小值和最大值即可
void CalMulMax(int A[ ],int res[ ],int n){
int B; //表示A[1..n-1]中的最大值
int C; //表示A[1..n-1]中的最小值
B = A[n-1];
C = A[n-1];
res[n-1] = A[n-1]*A[n-1];
//计算res数组，最大值只可能是A[i]*B[i]或A[i]*C[i]
for(int i=n-2;i>=0;i++)
B = max(B,A[i]);
C = max(C,A[i]);
res[i] = max(A[i]*B,A[i]*C);
}
}
时间复杂度O(n)
空间复杂度O(1)

2024