优化大规模数组多次更新操作的时间复杂度问题

嘿，我明白你的痛点——当命令数达到1e9级别时，每次type2命令都遍历整个1e5大小的数组，这完全是灾难级的时间消耗，根本跑不完对吧？咱们换个思路，不用每次都去修改数组里的每一个元素，而是用全局阈值记录+延迟计算的方式来解决这个问题。

核心思路 #

问题里的type2命令本质是给数组设置一个“最低底线”：所有小于r的元素都要提升到r。那我们可以不用立刻修改所有元素，而是把这个底线记下来，每个元素的实际值其实是它被设置的原始值和这个底线的最大值。这样，type2命令只需要更新底线，type1命令只需要记录元素的原始设置值，最后统一计算结果就行，完全避免了大规模遍历。

具体实现步骤 #

1. 初始化准备

   • 先复制一份原数组到stored数组里，这个数组专门用来记录每个元素被type1命令设置的原始值（初始状态就是原数组的值）。
   • 初始化一个变量globalFloor为整数最小值（Integer.MIN_VALUE），用来表示当前的全局最低底线，初始时因为没有type2命令，所有元素的实际值就是stored里的原值。

2. 处理每个命令

   • 对于type1命令（[1,p,q]）：直接把stored[p]设为q就行，这一步是O(1)操作，快得很。
   • 对于type2命令（[2,-1,r]）：只需要把globalFloor更新为max(globalFloor, r)。为啥？如果r比当前底线小，那这个命令没啥用（所有元素的实际值已经不低于当前底线，自然也不低于r）；如果r更大，那新的底线就是r，之后所有元素的实际值都会取自身存储值和r的最大值。这一步也是O(1)。

3. 生成最终结果
   等所有命令处理完，咱们再遍历一次stored数组，每个元素取max(stored[i], globalFloor)作为最终值，把这些值放到结果数组里就行。这一步是O(n)，对于1e5的数组来说，完全是小菜一碟。

用你的例子验证 #

咱们拿你给的例子走一遍流程：

• 初始A = [2,4,1,4]，所以stored初始为[2,4,1,4]，globalFloor是Integer.MIN_VALUE。
• 命令1：[1,1,30] → stored[1] = 30，stored变成[2,30,1,4]。
• 命令2：[1,2,4] → stored[2] =4，stored变成[2,30,4,4]。
• 命令3：[2,-1,10] → globalFloor更新为max(MIN_VALUE,10)=10。
• 生成结果：每个元素取max(stored[i],10) → [10,30,10,10]，和你的预期完全一致。

Java代码实现 #

import java.util.Arrays;

public static int[] solve(int n, int[] A, int[][] commands) {
    // 存储每个元素的原始设置值
    int[] stored = Arrays.copyOf(A, n);
    int globalFloor = Integer.MIN_VALUE;

    for (int[] command : commands) {
        if (command[0] == 1) {
            int p = command[1];
            int q = command[2];
            stored[p] = q;
        } else if (command[0] == 2) {
            int r = command[2];
            if (r > globalFloor) {
                globalFloor = r;
            }
        }
    }

    // 计算最终结果
    int[] result = new int[n];
    for (int i = 0; i < n; i++) {
        result[i] = Math.max(stored[i], globalFloor);
    }

    return result;
}

复杂度分析 #

• 时间复杂度：处理m个命令是O(m)，生成结果是O(n)，总时间O(m + n)。不管命令数是1e9还是更多，每个命令都是O(1)操作，完全不会超时。
• 空间复杂度：O(n)，需要一个和原数组一样大的stored数组，对于1e5的规模来说，内存完全够用。

备注：内容来源于stack exchange，提问作者Learner