LeetCode42接雨水

Question

int min(int a,int b){
    return a<b?a:b;
}
void swap(int* a,int* b){
    int temp=*a;
    *a=*b;
    *b=temp;
}

int getrain(int* a,int left,int right){
    if(left+1>=right) return 0;
    int max1=0,max2=0;
    int index1=-1,index2=-1;
    for(int i=left;i<=right;i++){
        if(a[i]>=max1){
            max2=max1;
            index2=index1;
            max1=a[i];     
            index1=i;
        }
    }
    if(index2<index1){//index1始终指向左边，indexe2始终指向右边；
        swap(&index1,&index2);
       // swap(&max1,&max2);
    }
    int w=0;
    for(int i=index1+1;i<index2;i++){
       w+=a[i];//index1和index2之间墙的体积
    }
    int sum=(min(a[index1],a[index2])*(index2-index1-1))-w;
    if(sum<0) sum=0;
    return sum+getrain(a,left,index1)+getrain(a,index2,right);
}


int trap(int* height, int heightSize) {
        return getrain(height,0,heightSize-1);
}

求出最高的柱子和次高的柱子，然后递归计算区域两侧，为什么运行报错呢

Answer 1

阿里嘎多学长整理AIGC生成，因移动端显示问题导致当前答案未能完全显示，请使用PC端查看更加详细的解答过程

LeetCode42接雨水

你的问题是关于 LeetCode42 接雨水问题的解决方案。

问题描述：给定 n 个非负整数 a1,a2,...,an，表示每个位置的高度，我们需要找到能容纳雨水的最大面积。

我的解决方案是使用双指针法，初始化两个指针 i 和 j，分别指向数组的开始和结束。然后，我们不断地移动指针，使得当前指针所指向的高度小于或等于其他指针所指向的高度。这样，我们可以确保当前指针所指向的高度是当前能容纳雨水的最大高度。

下面是我的解决方案的核心代码：

int trap(int* height, int heightSize) {
    int left = 0, right = heightSize - 1;
    int maxLeft = 0, maxRight = 0;
    int res = 0;
    while (left <= right) {
        if (height[left] < height[right]) {
            if (height[left] >= maxLeft) {
                maxLeft = height[left];
            } else {
                res += maxLeft - height[left];
            }
            left++;
        } else {
            if (height[right] >= maxRight) {
                maxRight = height[right];
            } else {
                res += maxRight - height[right];
            }
            right--;
        }
    }
    return res;
}

这个解决方案的时间复杂度是 O(n)，空间复杂度是 O(1)。