leetcode_trapping_rain_water

发表于

难度：Medium

解题思路：本题卡了好久。后来想到一种解法，找出数组的最大值a和第二大值b，这两个值将整个数组分成三个区域，左、中、右。中间区域的存水量，可以求得。左和右的存水量继续调用函数即可。
代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
class Solution {
public:
    int trap(vector<int>& height) {
        if(height.size()==0 ||height.size()==1) return 0;
        return trap_with_segment(height,0,height.size()-1);
    }
    int trap_with_segment(vector<int>& height, int left_index, int right_index)
    {
        if(left_index == right_index || left_index+1 == right_index)
            return 0;
        int first_max_index = left_index;
        int second_max_index = right_index;
        int first_max = INT_MIN;
        int second_max = INT_MIN;
        for(int i = left_index; i <= right_index; i++)
        {
            if(height[i] >= first_max)
            {
                second_max_index = first_max_index;
                second_max = first_max;
                first_max_index = i;
                first_max = height[i];
            }
            else
            {
                if(height[i] >= second_max)
                {
                    second_max_index = i;
                    second_max = height[i];
                }
            }
        }
        int min_height = second_max;
        int left_max_index = first_max_index < second_max_index?first_max_index:second_max_index;
        int right_max_index = first_max_index < second_max_index?second_max_index:first_max_index;
        // cout<<"left_max_index: "<<left_max_index<<" "<<"right_max_index: "<<right_max_index<<endl;
        if(left_max_index == right_max_index || left_max_index+1 == right_max_index)
        {
            return trap_with_segment(height,left_index,left_max_index)+trap_with_segment(height,right_max_index,right_index);
        }
        else
        {
            // int min_height = min(height[left_max_index],height[right_max_index]);
            int filled = 0;
            for(int i = left_max_index+1; i < right_max_index;i++)
                filled += height[i];
            int sum = (right_max_index-left_max_index-1)*min_height-filled;
            return sum+trap_with_segment(height,left_index,left_max_index)+trap_with_segment(height,right_max_index,right_index);
        }
    }
};

运行结果：12ms，超过18.07％

另一种解法：

求的每一个点上面，能存多少水，然后相加。从后往前遍历，存储每一个点右边的最高点。从前往后遍历，查得到左边的最高点，看看是不是都比它高，如果是则可以存水；否则无法存水。
代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution {
public:
    int trap(vector<int>& height) {
        int right_max = INT_MIN;
        vector<int> right_max_vec(height.size());
        for(int i = height.size()-1; i >= 0; i--)
        {
            right_max = (height[i] > right_max)?height[i]:right_max;
            right_max_vec[i] = right_max;
            //right_max为从i到数组结尾的元素的最大值，包含i
        }
        
        int left_max = INT_MIN;
        int sum = 0;
        for(int i = 0; i < height.size(); i++)
        {
            left_max = (height[i] > left_max)?height[i]:left_max;
            //left_max为从数组开头到i的元素的最大值，包含i。
            int min_height = min(left_max,right_max_vec[i]);
            if(min_height > height[i])
                sum += min_height-height[i];
        }
        return sum;
    }
};

运行结果：9ms，超过30.10%