接雨水 - 困难

*************

C++

topic: 42. 接雨水 - 力扣（LeetCode）

*************

Give the topic an inspection.

Ley's try something hard. before solve this problem, I still begin my 涩话. In fact, I go to the concert in Zhenjiang, the singer is Xusong. I listen his song since my middle school. At the end of the last class in the moring, 玫瑰花的葬礼 reminded us 'go for lunch, kids'. And once I heard this song and I will be hungary for a short time. Middle school age is a beautiful time. I am aware that time is limited. I should pay more time to experience somrthing reallly fun. If I can be right back to my middle school, I will tell that little kid 'hey kid, donot wear that fucking glasses, that's not cool.'

Back to the topic and try something kind of hard. The key point is thinking like a computer. Iterate through all the array is possible. So think about it, caculate each position which can drink how many glasses of rains and summate them.

For position[i], find the tallest one on the left and the tallest one on the right, the glasses of rains is min(max_left, max_right) - position[i[.

then the code can start.

class Solution {
public:int trap(vector<int>& height) {int n      = height.size();int result = 0;for (int i = 1; i < n - 1; i++){// find the max value on the left// find the max value on the right// result = result + current_result}}
};

find the max value on the left and right.

        // 遍历每个柱子（除了第一个和最后一个，因为它们无法形成积水）for (int i = 1; i < n - 1; i++) {int left_max = 0; // 初始化左边的最大高度int right_max = 0; // 初始化右边的最大高度// 找到当前柱子左边的最大高度for (int j = i - 1; j >= 0; j--) {left_max = max(left_max, height[j]);}// 找到当前柱子右边的最大高度for (int j = i + 1; j < n; j++) {right_max = max(right_max, height[j]);}

summate the result.

            int current_result = min(left_max, right_max) - height[i];if (current_result > 0) {result += current_result;

and the total code is as follow.

class Solution {
public:int trap(vector<int>& height) {int n      = height.size();int result = 0;for (int i = 1; i < n - 1; i++){// find the max value on the leftint left_max  = 0;int right_max = 0;// 找到当前柱子左边的最大高度for (int j = i - 1; j >= 0; j--) {left_max = max(left_max, height[j]);}// 找到当前柱子右边的最大高度for (int j = i + 1; j < n; j++) {right_max = max(right_max, height[j]);}// 当前柱子能接的雨水量等于 min(left_max, right_max) - height[i]// 如果这个值小于0，说明当前柱子无法接水，直接跳过int current_result = min(left_max, right_max) - height[i];if (current_result > 0) {result += current_result;}// find the max value on the right// result = result + current_result}return result;}
};

This is not my first time to do this project and I still cannot write the code at once. Need more practice. But the good news is that I have the concept to solve the problem.