求蓄水量的ios解法（个人思路）

021F74458CCAF859C9B786C21B37CA51.jpg

---

偶然在QQ群里看到的题，心血来潮尝试一下
最初设想的方案如下：

---

    - (void)sumLearn {
    int max = 0;//数组最大元素的值
    int min = 100;//数组最小元素的值
    int total = 0;//积水面积
//    NSArray *arr = @[@(3), @(5), @(4), @(3), @(1), @(2), @(3), @(5), @(1), @(2)];
//    NSArray *arr = @[@(0), @(1), @(0), @(2), @(1), @(0), @(1), @(3), @(2), @(1), @(2), @(1)];
    NSArray *arr = @[@(0), @(2), @(5), @(1), @(3), @(0), @(2), @(4), @(3), @(1), @(0), @(2), @(0)];//数据源
    //先求出数组中最大最小h值
    for (int i = 0; i < arr.count; i++) {
        if (max < [arr[i] intValue]) {
            max = [arr[i] intValue];
        }
        if (min > [arr[i] intValue]) {
            min = [arr[i] intValue];
        }
    }
    //从最小值开始遍历，求和每个index下能盛水量
    for (int i = min; i <= max; i++) {
        //头尾不会盛水，不满足两侧为墙的条件
        for (int j = 1; j < arr.count - 1; j++) {
            if ([arr[j] intValue] == i) {
                //原理 当左右都有墙时，选最矮的墙与本次遍历最低点求差值 即为本次index下能盛水量
                BOOL wall1 = NO;//左围墙
                BOOL wall2 = NO;//右围墙
                int max1 = 0;//左围墙最大值
                int max2 = 0;//右围墙最大值
                for (int x = 0; x < j; x++) {
                    if ([arr[x] intValue] > i) {
                        //在左侧  并且左墙比当前高
                        wall1 = YES;
                    }
                }
                for (int y = j; y < arr.count; y++) {
                    if ([arr[y] intValue] > i) {
                        //在右侧  并且右墙比当前高
                        wall2 = YES;
                    }
                }
                
                for (int x = 0; x < j; x++) {
                    if ([arr[x] intValue] > max1) {
                        //左墙最大值
                        max1 = [arr[x] intValue];
                    }
                }
                for (int y = j; y < arr.count; y++) {
                    if ([arr[y] intValue] > max2) {
                        //右墙最大值
                        max2 = [arr[y] intValue];
                    }
                }
                
                if (wall1 && wall2) {//符合条件，符合左右都有高墙
                    //取矮墙与当前高度差值 即此次能盛水量
                    if (max1 > max2) {
                        total += (max2 - i);
                    } else {
                        total += (max1 - i);
                    }
                }
            }
        }
    }
    NSLog(@"-----------total = %d", total);
}

---

期间发现包含无用步骤，优化后代码如下：

---

- (void)sumLearn2 {
    int total = 0;//积水面积
    NSArray *arr = @[@(3), @(5), @(4), @(3), @(1), @(2), @(3), @(5), @(1), @(2)];
    
    //头尾不会盛水，不满足两侧为墙的条件
    for (int i = 1; i < arr.count - 1; i++) {
        int value = [arr[i] intValue];
        //原理 当左右都有墙时，选最矮的墙与本次数值求差值 即为本次i下能盛水量
        
        //默认左墙高度0
        int max1 = 0;
        //默认右墙高度0
        int max2 = 0;
        
        for (int j = 0; j < i; j++) {
            if ([arr[j] intValue] > max1) {
                max1 = [arr[j] intValue];
            }
        }
        for (int k = i + 1; k < arr.count; k++) {
            if ([arr[k] intValue] > max2) {
                max2 = [arr[k] intValue];
            }
        }
        //当左右墙均比本次值大时 证明本次有积水
        if (max1 > value && max2 > value) {
            //取较矮一侧墙与本次值求差 累计积水面积
            if (max1 > max2) {
                total += (max2 - value);
            } else {
                total += (max1 - value);
            }
        }
    }
    NSLog(@"====================total = %d", total);
}