收集雨水算法复杂度

Question

正在尝试解决 Trapping Rain Water 问题，但无法理解为什么我的解决方案未通过复杂性检查：

    public int Trap(int[] height) {
        int res = 0;
        int chk = 0;
        for(int i = 1; i < height.Length; i++){
            chk = Math.Min(height[..i].Max(),height[i..].Max())-height[i];
            if(chk > 0){
                res += chk;
            }
        }
        return res;
    }

Compile:    0.024s
Execute:    0.85s
Memory: 3.90Mb
CPU:    0.874s

但是这个（推荐）通过了：

    public int Trap(int[] land) {
       var wall = 0;
        var water = new int[land.Length];
        for(var i = 0; i < water.Length; i++) {
            wall = Math.Max(wall, land[i]);
            water[i] = wall - land[i];
        }
        wall = 0;
        var sum = 0;
        for(var i = water.Length - 1; i >= 0; i--) {
            wall = Math.Max(wall, land[i]);
            water[i] = Math.Min(water[i], wall - land[i]);
            sum += water[i];
        }
        return sum;
    }

Compile:    0.024s
Execute:    0.03s
Memory: 0b
CPU:    0.054s

为什么差别这么大？是因为数组slice[..i]?

Answer 1

数组切片操作的时间复杂度为O(N)。
因此，您的代码的总时间复杂度变为 O(N²)。
这就是 TLE.

的原因

虽然推荐的代码仅在 O(N) 时间复杂度内解决了该问题。

收集雨水算法复杂度

Trapping rain water algorithm complexity

c#

algorithm

complexity-theory