You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
82 lines
3.3 KiB
82 lines
3.3 KiB
// 接雨水问题
|
|
#include<iostream>
|
|
using namespace std;
|
|
/*
|
|
*暴力法：每个柱子顶部可以储水的高度为：该柱子的左右两侧最大高度的较小者减去此柱子的高度。因此我们只需要遍历每个柱子，累加每个柱子可以储水的高度即可。
|
|
*/
|
|
int JieYuShui1(int height[], int len){
|
|
int res = 0;
|
|
// 遍历每个柱子
|
|
for (int i = 1; i < len - 1; i++) {
|
|
int leftMax = 0, rightMax = 0;
|
|
// 计算当前柱子左侧的柱子中的最大高度
|
|
for (int j = 0; j <= i; j++) {
|
|
leftMax = max(leftMax, height[j]);
|
|
}
|
|
// 计算当前柱子右侧的柱子中的最大高度
|
|
for (int j = i; j < len; j++) {
|
|
rightMax = max(rightMax, height[j]);
|
|
}
|
|
// 结果中累加当前柱子顶部可以储水的高度，
|
|
// 即 当前柱子左右两边最大高度的较小者 - 当前柱子的高度。
|
|
res += min(leftMax, rightMax) - height[i];
|
|
}
|
|
return res;
|
|
}
|
|
|
|
/*
|
|
*动态规划：对于每个柱子，我们都需要从两头重新遍历一遍求出左右两侧的最大高度，这里是有很多重复计算的，很明显最大高度是可以记忆化的，具体在这里可以用数组边递推边存储，也就是常说的动态规划，DP。
|
|
1定义二维dp数组 int[][] dp = new int[n][2]，其中，dp[i][0] 表示下标i的柱子左边的最大值，dp[i][1] 表示下标i的柱子右边的最大值。2分别从两头遍历height数组，为 dp[i][0]和 dp[i][1] 赋值。3同方法1，遍历每个柱子，累加每个柱子可以储水的高度。
|
|
*/
|
|
int JieYuShui2(int height[], int len){
|
|
int res = 0;
|
|
if (len == 0) {
|
|
return 0;
|
|
}
|
|
// 定义二维dp数组
|
|
// dp[i][0] 表示下标i的柱子左边的最大值
|
|
// dp[i][1] 表示下标i的柱子右边的最大值
|
|
|
|
int dp[len][2];
|
|
dp[0][0] = height[0];
|
|
dp[len - 1][1] = height[len - 1];
|
|
for (int i = 1; i < len; i++) {
|
|
dp[i][0] = max(height[i], dp[i - 1][0]);
|
|
}
|
|
for (int i = len - 2; i >= 0; i--) {
|
|
dp[i][1] = max(height[i], dp[i + 1][1]);
|
|
}
|
|
// 遍历每个柱子，累加当前柱子顶部可以储水的高度，
|
|
// 即 当前柱子左右两边最大高度的较小者 - 当前柱子的高度。
|
|
for (int i = 1; i < len - 1; i++) {
|
|
res += min(dp[i][0], dp[i][1]) - height[i];
|
|
}
|
|
return res;
|
|
}
|
|
|
|
/*
|
|
*双指针：在上述的动态规划方法中，我们用二维数组来存储每个柱子左右两侧的最大高度，但我们递推累加每个柱子的储水高度时其实只用到了 dp[i][0]和 dp[i][1] 两个值，因此我们递推的时候只需要用 int leftMax 和 int rightMax 两个变量就行了。
|
|
*/
|
|
int JieYuShui3(int height[], int len){
|
|
int res = 0;
|
|
int leftMax = 0, rightMax = 0, left = 0, right = len - 1;
|
|
while (left <= right) {
|
|
if (leftMax <= rightMax) {
|
|
leftMax = max(leftMax, height[left]);
|
|
res += leftMax - height[left++];
|
|
} else {
|
|
rightMax = max(rightMax, height[right]);
|
|
res += rightMax - height[right--];
|
|
}
|
|
}
|
|
return res;
|
|
}
|
|
|
|
int main(){
|
|
int arr[] = {0,1,0,2,1,0,1,3,2,1,2,1};
|
|
int len = sizeof(arr) / sizeof(arr[0]);
|
|
int res = JieYuShui3(arr, len);
|
|
cout<<res<<endl;
|
|
return 0;
|
|
}
|
|
|