稀碎从零算法笔记Day31-LeetCode:接雨水

半月一去，望舒一轮，明天开始攻坚哈德题了

前言：非常经典的一道笔试题，看了保证血赚（今天银泰星笔试第四题就是这个）

题型：dp、模拟、双指针……

链接：42. 接雨水 - 力扣（LeetCode）

来源：LeetCode

方法好多，这里用的“F大佬”的双指针思路

题目描述

本题为Hard题，建议配合样例&题解食用

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

题目样例

示例 1：

蓝色方块为雨水“个数”

输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 

示例 2：

输入：height = [4,2,0,3,2,5]
输出：9

提示：

• n == height.length
• 1 <= n <= 2 * 104
• 0 <= height[i] <= 105

题目思路

初见这道题是银泰星的笔试第四道，道理明白，但是不知道怎么实现

这时候一股神秘的“东方力量”：dp，dp呀~

OK，那笔者就写一下自己用DP的做法（二周目，一周目是BE//(ㄒoㄒ)/~~）

能接到雨水，归根到底是保证两边的柱子高，中间柱子矮，那就可以存水。

这边可以把这种结构想象成【木桶】——那么影响木桶盛水的因素就是木桶的短板。虽然很抽象，但可以把相邻柱子的边看作是【木桶的板】，那么这个【木桶】能盛水的量，就是min（左板，右板）- height[i] 。

一个木桶是这样的，如果不断地扩大木桶的个数，那就相当于DP中的 将子问题放大了。

                ​​​​​​​        ​​​​​​​        ​​​​​​​        

当然断不可【无脑放大】——即只看相邻的柱子的高度。这部分，要想求得水的高度，说明【相邻最大的边】这个条件是不行的。这时候不难发现，应该是【右/左边最大的边】。这时候带入样例就合理多了。

那么获得【右/左边最长的边】，即获得两个方向最高柱子的高度，就是本题DP的破局点。
以求【往左走，经历过最高的柱子高度】为例，dpL[i] 表示 i 这个索引左边中，最高的柱子的高度。
可以dpL[i]会经历两个状态：①如果dpL[i-1] 比height[i]大，那k继续往左走，因为他之前的柱子中就有比height[k]高的 ② 如果dpL[k-1]要小的话，那就乖乖把dpL[i] 更新为height[i] 。

那么递归式就是： dp[i] = max(dp[i-1] , height[i])

因为木桶有两边的缘故，自然要求相反走向的【最高的柱子高度】

C++代码

dp，用了两个数组

class Solution {
public://银泰星笔试int trap(vector<int>& height) {int len = height.size();if(len <3)return 0;// 要确定动态申请数组的元素的个数，要不会野指针vector<int> dp_left(len);//从左边开始走vector<int> dp_right(len);//从右边开始走dp_left[0] = height[0];dp_right[len-1] = height[len-1];for(int i=1;i<len;i++){dp_left[i] = max(dp_left[i-1],height[i]);}for(int i=len-2;i>=0;i--){dp_right[i] = max(dp_right[i+1],height[i]);}int ans = 0;for(int i=0;i<len;i++){int temp = min(dp_left[i],dp_right[i]) - height[i];if(temp > 0)ans += temp;}return ans;}
};

结算页面 

dp