最多1次交换下最大化数组指定元素差值的算法问题

先把问题再明确下，避免理解偏差：

给定数组A，数组的“幂值”是所有满足2≤i≤N的i对应的A[i]−A[j]的最大值（其中j是i之前最大的索引且满足A[j] < A[i]）。我们最多可以执行1次交换操作（交换任意两个元素的位置），需要找到交换后能得到的最大幂值。
示例：数组{11,12,15}的幂值是max((12−11),(15−12))=3。

我当时琢磨这个问题的时候，是从“先搞懂基准，再找增益”的思路入手的：

第一步：计算原数组的基准幂值 #

首先得算出不做任何交换时的幂值original_power，这是我们的底线——交换后的结果至少不能比这个差。计算原幂值的逻辑很直接：遍历数组，对每个i（对应题目里的2≤i≤N，也就是数组索引1到N-1），维护一个“i之前最大的小于A[i]的元素”，计算差值，记录最大值就行。

第二步：分析交换能带来增益的核心场景 #

交换的目的要么是让某个原本的差值变大，要么是创造出原本不存在的有效差值（比如原数组里某个i前面全是比它大的元素，交换后前面出现了更小的元素，就能贡献差值了）。重点关注这几种关键情况：

情况1：全局最大值在最前，全局最小值在最后 #

这种情况原数组的幂值通常很小（比如数组{15,12,11}，原幂值为0，因为每个i前面的元素都比它大，找不到符合条件的j）。这时候可以考虑两种交换方向：

• 交换次大值和全局最小值，计算新的幂值
• 交换全局最大值和次小值，计算新的幂值
  取这两个结果里的较大者，再和原幂值比较，选最大的。

情况2：存在某个元素A[i]，交换后能放大它的差值 #

比如：

• 把A[i]前面的某个元素换成更小的（比如把全局最小值换到A[i]前面的某个位置），这样A[i]-A[j]会变大
• 把A[i]换成更大的元素（比如把全局最大值换到A[i]的位置），让它和前面的A[j]差值更大
  这里要注意，j必须是i之前最大的满足A[j]<A[i]的索引，所以不能只看“有没有更小的元素在前面”，还要确保这个元素是i之前最后一个比它小的。

情况3：交换后创造出新的有效差值 #

比如原数组里有个元素A[i]，前面所有元素都比它大，所以这个i不贡献差值。如果我们把一个比A[i]小的元素交换到i前面的某个位置，这个i就能贡献A[i]-交换过来的元素的差值，要是这个差值足够大，就能拉高整体幂值。

第三步：高效计算最优解的小技巧 #

如果数组规模不大（比如n≤1000），可以直接遍历所有可能的交换对（i,j），交换后计算新的幂值，记录最大值——虽然是O(n²)的时间，但实现简单，不容易出错。

如果数组规模很大，就需要提前预处理一些信息：

• 前缀的最小值、次小值，以及它们的位置
• 后缀的最大值、次大值，以及它们的位置
• 每个位置i对应的“前一个比它小的最大索引j”和对应的差值
  然后基于这些预处理信息，快速判断哪些交换能带来最大增益，不用遍历所有交换对。

举个实际例子：原数组{15,12,11}，原幂值是0。交换15和11得到{11,12,15}，新幂值是3；交换15和12得到{12,15,11}，新幂值是3。所以最大幂值就是3。

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