数组中满足a[i]≤a[j]（i<j）的最大索引差代码错误排查

首先，咱们先找一个能触发你代码错误的测试用例：输入数组[5,4,1,2,3]。正确的最大索引差是2（i=2，j=4，满足1<=3，索引差为4-2=2），但你的代码会返回1，这就能帮咱们定位问题了。

你的代码核心错误 #

1. 提前终止循环，跳过有效组合
   你的代码在遇到某些不满足a[j]>=a[i]的情况时，会直接break终止循环，导致错过更优的i、j组合。比如刚才的测试用例：当i=1,j=3时，你的代码因为a[j] >= a[i+1]（2>=1）就立刻停止了，完全没机会检查到i=2,j=4这个更优的配对。

2. 错误的逻辑假设
   你默认如果两端元素不满足条件，最大差只能是j-i-1，但问题的核心是要找到尽可能靠左的i和尽可能靠右的j（i<j）使得a[i]<=a[j]，这种假设完全不成立，很多更优的配对出现在数组中间位置。

正确的解法思路 #

我们可以用O(n)时间、O(n)空间的方法来解决这个问题，核心是先预处理出两个辅助数组：

• min_left[i]：表示从数组开头到索引i的最小值（快速知道每个位置左边最小的元素）
• max_right[j]：表示从索引j到数组末尾的最大值（快速知道每个位置右边最大的元素）

然后用双指针遍历这两个数组，找到最大的j-i满足min_left[i] <= max_right[j]。

修正后的代码 #

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int t, n;
    cin >> t;
    while (t--) {
        cin >> n;
        vector<long long> a(n);
        for (int i = 0; i < n; ++i) {
            cin >> a[i];
        }

        // 构建min_left数组：min_left[i]是a[0..i]的最小值
        vector<long long> min_left(n);
        min_left[0] = a[0];
        for (int i = 1; i < n; ++i) {
            min_left[i] = min(min_left[i-1], a[i]);
        }

        // 构建max_right数组：max_right[j]是a[j..n-1]的最大值
        vector<long long> max_right(n);
        max_right[n-1] = a[n-1];
        for (int j = n-2; j >= 0; --j) {
            max_right[j] = max(max_right[j+1], a[j]);
        }

        int i = 0, j = 0, max_diff = 0;
        while (i < n && j < n) {
            if (min_left[i] <= max_right[j]) {
                // 当前i对应的最小元素 <= j对应的最大元素，尝试更大的j来扩大差
                max_diff = max(max_diff, j - i);
                ++j;
            } else {
                // 当前i的最小元素太大，需要移动i找更小的元素
                ++i;
            }
        }

        cout << max_diff << "\n";
    }
    return 0;
}

代码解释 #

1. 辅助数组构建：min_left帮我们快速定位每个位置左边最小的元素，max_right帮我们快速定位每个位置右边最大的元素，这样不用每次都重新遍历数组找最值。
2. 双指针遍历：
   • 当min_left[i] <= max_right[j]时，说明存在某个k<=i和l>=j使得a[k]<=a[l]，我们可以尝试把j右移，看看能不能得到更大的索引差。
   • 当不满足时，说明当前i对应的最小元素太大，需要把i右移，找更小的元素来尝试匹配。

这种方法能保证我们找到最大的索引差，而且时间复杂度是O(n)，效率很高。

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