临时变量是否会导致算法不再是原地算法？附连续最大列表算法示例

首先直接给结论：不会，使用单个临时变量的算法依然属于原地算法。

原地算法的核心定义 #

原地算法的关键特征是：使用的辅助空间与输入数据的规模无关，即空间复杂度为O(1)。这里的辅助空间指的是除了输入本身占用的内存之外，额外申请的存储空间。单个临时变量（比如你代码里的temp）属于常数级空间开销——不管输入数组的长度n是10还是10000，这个变量只占用固定大小的内存，完全符合原地算法的要求。

你的原地算法分析 #

先回顾你实现的原地算法代码：

void inConMax(int a[],int n) {
 int temp = -INFINITY;
 for (int i=0;i<n;i++) {
 if(temp>a[i]) {
 int k = temp;
 temp = a[i];
 a[i]=k;
 } else {
 temp=a[i];
 }
 }
}

这个算法通过维护一个临时变量temp来跟踪当前遍历到的最大元素，在遍历过程中直接修改原数组，没有申请任何与n相关的额外空间（比如非原地版本里的maxA数组）。

结合你的输入示例验证：
输入数组：{7,5,9,23,24,6,4,19,20}
遍历过程中数组的变化完全符合规则a(i+1)=max(a(i),a(i+1))，最终输出结果：7 7 9 23 24 24 6 19 20，算法逻辑是正确的。

对比非原地版本 #

你的非原地算法：

void conMax(int A[], int maxA[],int n) {
 for (int i=0;i<n;i++) {
 if (A[i]>=A[i-1]) { // 注：这里i=0时A[i-1]会越界，需要修正边界条件
 maxA[i]=A[i];
 } else {
 maxA[i]=A[i-1];
 }
 }
}

这里额外申请了一个长度为n的数组maxA，空间复杂度为O(n)，不属于原地算法；而原地版本只用了O(1)的辅助空间，这正是原地算法的优势所在。

补充小提示 #

你的非原地算法存在一个边界问题：当i=0时，访问A[i-1]会导致数组越界，建议修正为：

void conMax(int A[], int maxA[],int n) {
 if (n == 0) return;
 maxA[0] = A[0];
 for (int i=1;i<n;i++) {
 if (A[i]>=maxA[i-1]) { // 用maxA[i-1]代替A[i-1]，符合连续最大的规则
 maxA[i]=A[i];
 } else {
 maxA[i]=maxA[i-1];
 }
 }
}

内容的提问来源于stack exchange，提问作者trap28