42.接雨水(难度:困难)题目链接:https://leetcode-cn.com/problems/trapping-rain-water/题目描述:给定n个非负整数表示每个宽度为1的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。上面是由数组[0,1,0,2,1,0,1,3,2,1,2,1]表示的高度图,在这种情况下,可以接6个单位的雨水(蓝色部分表示雨水)。感谢Marcos贡献此图。示例:输入:[0,1,0,2,1,0,1,3,2,1,2,1]输出:6解法一:动态规划法我们可以,计算每一个位置,对应的左边最大值和右边最大值,即从这个位置,向左看,找到最高块的高度,设为他的左边最大