ThinkLeet/（柱状图型）2.1.15 Trapping Rain Water at master · YanjieGao/ThinkLeet · GitHub
Given n 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. For example, Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6. 图2-3 Trapping Rain Water 解法：左遍历，右遍历，求出每个柱子，最上方能称多少水。最后累加。时间复杂度o(n), 空间复杂度o(n) 变式：为为2D的模型来做。围住的空间是多大。 二维的解法： 方法1：类似trap water 方法2：可以反证法，求出x的空间然后总空间减去这个空间 三维也是同理，能够围住多少水 变式： （1）柱子内的最大长方形面积(4.1.3 Largest Rectangle in Histogram)：栈做，时间复杂度o(n)，空间复杂度o(n) (2)两个柱子组成的最大长方形面积：夹逼法，小的向里移动，（因为大的向内移动只能减少面积，小的还有希望扩展面积）。 时间复杂度o(n)空间法复杂度o(1) （3）生成新柱状图型：原始是权重柱子，新的柱状图每个节点如果权重大于neighbour则新的柱状图中也要值大于neighbor（2.1.22 Candy） 方法：左遍历,右遍历。时间复杂度o(n)，空间复杂度o(1) 变式：权重大的反而要小，只要把之前算法的权重改为-1值即可，算法仍可复用。 (4)Stock模型： 1 一天买卖一次：(12.3 Best Time to Buy and Sell Stock) 遍历，统计min和统计maxprofit，类似动归的思想 2 一天买卖n次：(12.4 Best Time to Buy and Sell Stock II) 差分数组。 3 一天买卖2次：(13.5 Best Time to Buy and Sell Stock III) 动归，分两种情况 第一类 两个事务相交 0 i n ，在0 i 和i n分别存在两个事务，然后每个里转化为问题1. 第二类 两个事务不相交 0 i n两个最小值在 0 i两个最大值在i n，从左遍历一次统计所在节点左侧的两个min ，从右遍历一次统计右侧的两个max，这个过程 就可以求出i点的maxprofict 时间复杂度 o(n2)空间复杂度 o(n) 4 变式：一天买卖k次：类似3一天买卖2次的处理方式.相比1,2要复杂 还是分类 1个和k-1个事务不相交： 0 i n，转换为子问题 f(1)和f(k) 1个和k-1个事务相交：分类和其中 1个，2个，3个。。。k个相交做。 （5）并行化（一般从头遍历，切求最值的不太好并行化）： 2.1.15 启示：可以思考多轮次做，前几轮进行元数据信息获取，或者进行sample 进行range分区，每个分区的柱子还是原顺序。 第一轮：获取这个分区的max高度。map为key（左右坐标），value（max高度），reduce更新各分区的左右做大高度。 第二轮：然后按照单机的做法求最大的水量Read full article from ThinkLeet/（柱状图型）2.1.15 Trapping Rain Water at master · YanjieGao/ThinkLeet · GitHub
No comments:
Post a Comment