【LeetCode】42. Trapping Rain Water（C++）

概述本文章向大家介绍【LeetCode】42. Trapping Rain Water（C++），主要包括【LeetCode】42. Trapping Rain Water（C++）使用实例、应用技巧、基本知识点总结和需要注意事项，具有一定的参考价值，需要的朋友可以参考一下。

地址：https://leetcode.com/problems/trapPing-rain-water/

题目：

Given nnn non-negative integers representing an elevation map where the wIDth of each bar is 1,compute how much water it is able to trap after raining.

The above elevation map is represented by array [0,1,2,3,1]. In this case,6 units of rain water (blue section) are being trapped.

Example:

input: [0,1]

Output: 6

理解：

寻找这个奇怪的容器可以装多少水。在位置i可以装的水取决于其左右两边的高边中较低的。例如对于上图中的5，左边最高为3，右边最高为7，所以可以装的水被3的高度所限制。

实现1：

基于动态规划的实现。为了避免每次重复寻找每个位置左右的最大元素，使用了两个数组，采用动态规划的思想保存位置i左边和右边的最大元素。基本思想是，对于i位置，其左边的最大值就等于i-1位置左边的最大值和height[i]两者中的最大值。同理，右侧的最大值要从右侧找到。

class Solution {

public:

int trap(vector& height) {

if (height.empty()) return 0;

int size = height.size();

vector left_max(size),right_max(size);

left_max[0] = height[0];

for (int i = 1; i < size; ++i)

left_max[i] = max(height[i],left_max[i - 1]);

right_max[size - 1] = height[size - 1];

for (int i = size - 2; i >= 0; --i)

right_max[i] = max(height[i],right_max[i + 1]);

int res = 0;

for (int i = 1; i < size - 1; ++i)

res += min(left_max[i],right_max[i]) - height[i];

return res;

}

};

实现2：

可以观察上面给出的两个left_max和right_max数组。当right_max[i]>left_max[i]的时候，水的体积取决于left_max，而left_max[i]>right_max[i]的时候，取决于right_max。若height[right]

class Solution {

public:

int trap(vector& height) {

int res = 0;

int left = 0,right = height.size() - 1;

int left_max = 0,right_max = 0;

while (left < right) {

if (height[left] < height[right]) {

height[left] >= left_max ? (left_max = height[left]) : (res += left_max - height[left]);

++left;

}

else {

height[right] >= right_max ? (right_max = height[right]) : (res += right_max - height[right]);

--right;

}

}

return res;

}

};

总结

以上是内存溢出为你收集整理的【LeetCode】42. Trapping Rain Water（C++）全部内容，希望文章能够帮你解决【LeetCode】42. Trapping Rain Water（C++）所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。