c语言做接雨水问题的

Question

int trap(int* height, int heightSize){
    if(heightSize==1)
    return 0;
    int i,j,k;
    int res=0;
    for(i=0;i<heightSize-1;i++){
        for(j=i+1;j<heightSize;j++){
            if(height[j]>=height[i]){
                for(k=i+1;k<j;k++){
                    res+=(height[i]-height[k]);
                }
                i=j;
                break;
            }
        }
    }
    if(height[0]<height[1]){
        res=res-(height[1]-height[0]);
    }
    return res;
}

为什么这样是错的，题目如下

Answer 1

你代码我运行了结果不对

#include <iostream>

using namespace std;
 
int trap(int* height, int heightSize){
    if(heightSize==1)
    return 0;
    int i,j,k;
    int res=0;
    for(i=0;i<heightSize-1;i++){
        for(j=i+1;j<heightSize;j++){
            if(height[j]>=height[i]){
                for(k=i+1;k<j;k++){
                    res+=(height[i]-height[k]);
                }
                i=j;
                break;
            }
        }
    }
    if(height[0]<height[1]){
        res=res-(height[1]-height[0]);
    }
    return res;
}
int main()
{
    int height[] = { 0,1,0,2,1,0,1,3,2,1,2,1 };
    int r = trap(height, 12);
    cout << r;
    return 0;
}

你的代码返回1

我写了一个，效率未必高，但是应该是对的

#include <iostream>

using namespace std;
 
int trap(int* height, int heightSize){
    int res = 0;
    int add;
    while (1)
    {
        add = 0;
        for (int i = 1; i < heightSize - 1; i++)
        {
            int curr = height[i] + 1;
            int bleft = 0;
            int bright = 0;
            for (int j = i - 1; j >= 0; j--)
            {
                if (height[j] >= curr) { bleft = 1; break; }
            }
            for (int j = i + 1; j < heightSize; j++)
            {
                if (height[j] >= curr) { bright = 1; break; }
            }
            if (bleft && bright)
            {
                height[i]++;
                add++;
            }
        }
        res += add;
        if (add == 0) break;
    }
    return res;
}
int main()
{
    int height[] = { 0,1,0,2,1,0,1,3,2,1,2,1 };
    int r = trap(height, 12);
    cout << r;
    return 0;
}