最近在玩图灵完备这个游戏的时候，突然卡关了，于是 搜索引擎 启动！！！

以下是我对这个问题的一些理解

思路


看到问题首先我就想到把每列的容量相加，而容量是min(左边最高的，右边最高的) - 当前高度，于是写出了以下代码

int trap(int* height, int heightSize){
    int lmax = 0, rmax = 0;
    int vol = 0;
    for(int i = 1; i < heightSize - 1; i++){

        for(int j = 0; j < i; j++){
            if(height[j] > height[lmax]){
                lmax = j;
            }
        }
        if(height[lmax] < height[i]){
            continue;
        }
		rmax = i + 1;
        for(int j = i + 1 ; j < heightSize ; j++){
            if(height[j] > height[rmax]){
                rmax = j;
            }
        }
        if(height[rmax] > height[i] && height[lmax] > height[i]){
            vol += height[rmax] > height[lmax] ? height[lmax] - height[i] : height[rmax] - height[i];
			lmax = 0;
            rmax = 0;
        }
    }
    return vol;
}

查询表（哈希表）改进

但是这段代码有几个问题

首先最大的问题就是时间复杂度过大，差不多有O(n^2)，这就导致运行速度奇慢无比

于是我就想到用动态规划（空间换时间的方法）来优化

int trap(int* height, int heightSize) {
    int lmax = 0, rmax = 0;
    int *lmax_arr = malloc((heightSize + 1)*sizeof(int));
    int *rmax_arr = malloc((heightSize + 1)*sizeof(int));
    int vol = 0;

    rmax_arr[heightSize] = heightSize - 1;
    for (int j = heightSize - 1; j >= 2; j--) {
        rmax = height[j] > height[rmax_arr[j + 1]] ? j : rmax_arr[j + 1];
        rmax_arr[j] = rmax;
    }

    for (int i = 1; i < heightSize - 1; i++) {

        lmax = height[i - 1] > height[lmax_arr[i - 1]] ? i - 1 : lmax_arr[i - 1];
        lmax_arr[i] = lmax;
        rmax = rmax_arr[i + 1];
        if (height[rmax] > height[i] && height[lmax] > height[i]) {
            vol += height[rmax] > height[lmax] ? height[lmax] - height[i] : height[rmax] - height[i];
            lmax = 0;
            rmax = 0;
        }
    }
    free(lmax_arr);
    free(rmax_arr);
    return vol;
}

这个方法利用了查表的方法，但是他的时间复杂度却还是O(2n)左右

于是我横竖睡不着，仔细看了半宿，才从字缝里看出字来，满篇都写着两个字是“优化”！

双指针的改进：

在这题中，lmax和rmax其实都只使用过一次，所以可以使用双指针交替前进，避免数组的使用。

其实就和查表的方法是差不多的，只不过把数组换成了一次性使用的lmax和rmax

不信的话你就自己看代码去吧

int trap(int* height, int heightSize) {      //双指针方法

    int l = 0, r = heightSize - 1;
    int sum = 0;
    int leftmax = 0;  //记录左边界最高
    int rightmax = 0;

    while(l < r){
        leftmax = leftmax > height[l] ? leftmax : height[l];
        rightmax = rightmax > height[r] ? rightmax : height[r];

        if(leftmax < rightmax){                    
            sum += (leftmax - height[l ++]);  //左边的边界更低
        }else{
            sum += (rightmax - height[r --]);
        }
    }

    return sum;
    
}