LeetCode题解:42. 接雨水 木灵的炼金工作室

题目描述

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。

输入: [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6

解题思路

首先发现关于本题的几条线索:

  1. 可以将整个区域分为数段来求算
  2. 决定每一段容量的是该区域柱子高度的最大值和次大值(次大值可与最大值相等)

所以解法就很明确了。

基本算法:

  1. 分治求解,先找到全局的最大值,分别向两边寻找次大值,找到之后求容量
  2. 接着以该次大值为新区域的最大值,继续向两侧寻找次大值。重复套娃直到触碰数组边界返回

注意事项: 需要仔细考虑的是水容量的计算方式,非常容易算多或者算少 有一个用例是空集,我特判掉了(逃)

开销: 还是不大的。理论时间O(n), 额外空间平均O(log n)

1.png

代码

//天知いのり 2020.4.18
class Solution {
public:
    int trap(vector<int>& height) {
        if (!height.size()) return 0; //空集特判
        int loca = 0;
        for (int i = 0; i < height.size(); i++)
            if (height[i] > height[loca]) loca = i; //寻找全局最大值的下标
        return left(height, loca) + right(height, loca);
    }
    int left(vector<int>& height, int start){
        if (start == 0) return 0;
        int loca = 0;
        for (int i = start - 1; i >= 0; i--)
            if (height[i] > height[loca]) loca = i;
        return calcu(height, loca, start) + left(height, loca);
    }
    int right(vector<int>& height, int start){
        if (start == height.size() - 1) return 0;
        int loca = height.size() - 1;
        for (int i = start + 1; i < height.size() - 1; i++)
            if (height[i] > height[loca]) loca = i;
        return calcu(height, start, loca) + right(height, loca);
    }
    int calcu(vector<int>& height, int start, int final_){ //避开final关键字(虽然说不避开也没什么啦
        int res = (height[start] < height[final_] ? height[start] : height[final_]) * (final_ - start + 1);
        for (int i = start; i <= final_; i++)
            res -= height[i] > (height[start] < height[final_] ? height[start] : height[final_]) ? (height[start] < height[final_] ? height[start] : height[final_]) : height[i];
        return res;
    }
};


Copyright AmachiInori 2017-2021. All Right Reserved.
Powered By Jekyll.
amachi.com.cn