塔之间收集水

最近我遇到了亚马逊问的一个面试问题，我无法find一个优化的algorithm来解决这个问题：

您将得到一个input数组，其中每个元素表示一个线塔的高度。 每个塔的宽度是1.开始下雨。 塔楼之间收集了多less水？

例

Input: [1,5,3,7,2] , Output: 2 units Explanation: 2 units of water collected between towers of height 5 and 7 * * *w* *w* *** **** ***** 

另一个例子

 Input: [5,3,7,2,6,4,5,9,1,2] , Output: 14 units Explanation= 2 units of water collected between towers of height 5 and 7 + 4 units of water collected between towers of height 7 and 6 + 1 units of water collected between towers of height 6 and 5 + 2 units of water collected between towers of height 6 and 9 + 4 units of water collected between towers of height 7 and 9 + 1 units of water collected between towers of height 9 and 2. 

起初我以为这可以通过库存量问题来解决，但是我错了，如果有人能想到时间的话，这个问题的优化algorithm。

Answer 1

一旦水落下，每个位置将填充到等于最高塔的左侧和最高塔的右侧较小的水平。

通过向右扫描find每个位置左边的最高塔。 然后通过向左扫描find每个位置右侧的最高塔。 然后把每个位置的最小值加起来。

像这样的东西应该工作：

 int tow[N]; // nonnegative tower heights int hl[N] = {0}, hr[N] = {0}; // highest-left and highest-right for (int i = 0; i < n; i++) hl[i] = max(tow[i], (i!=0)?hl[i-1]:0); for (int i = n-1; i >= 0; i--) hr[i] = max(tow[i],i<(n-1) ? hr[i+1]:0); int ans = 0; for (int i = 0; i < n; i++) ans += min(hl[i], hr[i]) - tow[i]; 

Answer 2

这是Haskell中一个有效的解决scheme

 rainfall :: [Int] -> Int rainfall xs = sum (zipWith (-) mins xs) where mins = zipWith min maxl maxr maxl = scanl1 max xs maxr = scanr1 max xs 

它使用与其他答案中提到的相同的两遍扫描algorithm。

Answer 3

请参考这个网站的代码，它非常简单和简单 http://learningarsenal.info/index.php/2015/08/21/amount-of-rain-water-collected-between-towers/

input：[5,3,7,2,6,4,5,9,1,2]，输出：14个单位

说明

每座塔可以容纳高达最高塔楼之间的最小高度的水平，最高的塔楼在右边。

因此，我们需要计算每座塔上最高的塔，左侧也是这样。

在这里，我们将需要两个额外的数组来保持最高塔的高度，在任何一个塔的左边，int leftMax []和right右边的int rightMax []。

步骤1

我们对给定数组（即int塔[]）进行左移，并将保持一个临时的最大值（比如int tempMax），使得每个塔的每个迭代高度将与tempMax进行比较，如果当前塔的高度小于tempMax，那么tempMax将被设置为最高塔的左侧，否则当前塔的高度将被指定为最高塔左侧，并且tempMax将被更新为当前塔的高度，

第2步

我们将按照上面的步骤，仅在步骤1中讨论计算最高的塔到右侧，但是这次从右侧进行穿过arrays。

STEP-3

每座塔可容纳的水量是 –

（最高右塔与最左塔之间的最小高度） – （塔的高度）

Answer 4

您可以通过两次扫描数组来完成此操作。

第一次从上到下扫描并存储到达每一行时还没有遇到的最高塔的价值。

然后你重复这个过程，但是相反。 您从底部开始，朝向arrays的顶部工作。 您可以跟踪迄今为止所见过的最高的塔楼，并将其高度与其他结果集中塔楼的高度相比较。

把这两个值中较小的那个（当前塔周围最高的两个塔中最短的一个，减去塔的高度，并把这个数值加到总的水量中）。

 int maxValue = 0; int total = 0; int[n] lookAhead for(i=0;i<n;i++) { if(input[i] > maxValue) maxValue = input[i]; lookahead[i] = maxValue; } maxValue = 0; for(i=n-1;i>=0;i--) { // If the input is greater than or equal to the max, all water escapes. if(input[i] >= maxValue) { maxValue = input[i]; } else { if(maxValue > lookAhead[i]) { // Make sure we don't run off the other side. if(lookAhead[i] > input[i]) { total += lookAhead[i] - input[i]; } } else { total += maxValue - input[i]; } } } 

Answer 5

可读的Python解决scheme：

 def water_collected(heights): water_collected = 0 left_height = [] right_height = [] temp_max = heights[0] for height in heights: if (height > temp_max): temp_max = height left_height.append(temp_max) temp_max = heights[-1] for height in reversed(heights): if (height > temp_max): temp_max = height right_height.insert(0, temp_max) for i, height in enumerate(heights): water_collected += min(left_height[i], right_height[i]) - height return water_collected 

Answer 6

Groovy中有两个解决scheme。

 assert waterCollected([1, 5, 3, 7, 2]) == 2 assert waterCollected([5, 3, 7, 2, 6, 4, 5, 9, 1, 2]) == 14 assert waterCollected([5, 5, 5, 5]) == 0 assert waterCollected([5, 6, 7, 8]) == 0 assert waterCollected([8, 7, 7, 6]) == 0 assert waterCollected([6, 7, 10, 7, 6]) == 0 def waterCollected(towers) { int size = towers.size() if (size < 3) return 0 int left = towers[0] int right = towers[towers.size() - 1] def highestToTheLeft = [] def highestToTheRight = [null] * size for (int i = 1; i < size; i++) { // Track highest tower to the left if (towers[i] < left) { highestToTheLeft[i] = left } else { left = towers[i] } // Track highest tower to the right if (towers[size - 1 - i] < right) { highestToTheRight[size - 1 - i] = right } else { right = towers[size - 1 - i] } } int water = 0 for (int i = 0; i < size; i++) { if (highestToTheLeft[i] && highestToTheRight[i]) { int minHighest = highestToTheLeft[i] < highestToTheRight[i] ? highestToTheLeft[i] : highestToTheRight[i] water += minHighest - towers[i] } } return water } 

在线编译器的代码片段如下： https : //groovy-playground.appspot.com/#?load=3b1d964bfd66dc623c89

Answer 7

您可以先左右移动，并计算左侧较小build筑物和右侧较大build筑物积水。 你将不得不减去在这两个build筑物之间的build筑物的面积，并且比左面的面积要小。

类似的情况是从右到左的情况。

这是从左到右的代码。 我已经上传这个问题在leetcode网上法官使用这种方法。

我发现这种方法比任何地方都存在的标准解决scheme（计算每个i的右侧和左侧最大的build筑物）更直观。

 int sum=0, finalAns=0; idx=0; while(a[idx]==0 && idx < n) idx++; for(int i=idx+1;i<n;i++){ while(a[i] < a[idx] && i<n){ sum += a[i]; i++; } if(i==n) break; jdx=i; int area = a[idx] * (jdx-idx-1); area -= sum; finalAns += area; idx=jdx; sum=0; } 

这种方法的时间复杂度是O（n），因为您正在线性遍历数组两次。 空间复杂性将是O（1）。

Answer 8

我丑陋的单遍历soln

 def water_collection(buildings): valleyFlag = False water = 0 pool = [] for i, building in enumerate(buildings): if(i == 0): lastHill = building else: if lastHill <= building or i == len(buildings)-1: minHill = min(building, lastHill) print("Hill {} to Hill {}".format(lastHill, building)) summ = 0 for drop in pool: summ += minHill - drop water += minHill - drop print("Collected sum {}".format(summ)) pool = [] valleyFlag = False lastHill = building elif lastHill > building and valleyFlag == False: pool.append(building) valleyFlag = True elif lastHill > building and valleyFlag == True: pool.append(building) print(water) 

Answer 9

这是另一个在Scala上编写的解决scheme

 def find(a: Array[Int]): Int = { var count, left, right = 0 while (left < a.length - 1) { right = a.length - 1 for (j <- a.length - 1 until left by -1) { if (a(j) > a(right)) right = j } if (right - left > 1) { for (k <- left + 1 until right) count += math.min(a(left), a(right)) - a(k) left = right } else left += 1 } count } 

Answer 10

O（n）解决scheme在Java中，一次通过

Java中的另一个实现是通过列表查找一次收集的水。 我扫描了其他答案，但没有看到明显使用我的解决scheme。

1. 通过循环列表find第一个“峰值”，直到塔高停止增加。 在此之前所有的水都不会被收集（排到左边）。
2. 对于所有后来的塔：
   • 如果后续塔的高度降低或保持不变，则将水添加到“潜在收集”桶中，等于塔高与之前最高塔高之间的差值。
   • 如果后续塔的高度增加，我们从前一个水桶中收集水（从“潜在收集”桶中减去并加到收集的桶中），并且将水加到潜在的桶中，等于塔高和塔以前的最高塔高。
   • 如果我们find一个新的最大塔，那么所有的“潜在的水”被移入收集的桶中，这成为新的最大塔高。

在上面的例子中，input：[5,3,7,2,6,4,5,9,1,2]，解决scheme的工作原理如下：

• 5：find5个第一个峰值
• 3：向潜在的桶（5-3）添加2

  收集= 0，潜力= 2

• 7：新的最大，将所有潜在的水移动到收集的桶

  收集= 2，潜力= 0

• 2：将5添加到潜在的桶（7-2）

  收集= 2，潜力= 5

• 6：将4移到收集的桶中，并将1加到潜在的桶（6-2,7-6）

  收集= 6，潜力= 2

• 4：向潜在的桶（6-4）添加2

  收集= 6，潜力= 4

• 5：将1移至收集的桶并将2join潜在的桶（5-4,7-5）

  收集= 7，潜力= 6

• 9：新的最大值，将所有潜在的水移动到收集的桶中

  收集= 13，潜力= 0

• 1：将8添加到潜在的桶（9-1）

  收集= 13，潜力= 8

• 2：将1移到收集的桶中，并将7添加到潜在的桶（2-1,9-2）

  收集= 14，潜力= 15

经过一次清单，收集到的水已经被测量。

 public static int answer(int[] list) { int maxHeight = 0; int previousHeight = 0; int previousHeightIndex = 0; int coll = 0; int temp = 0; // find the first peak (all water before will not be collected) while(list[previousHeightIndex] > maxHeight) { maxHeight = list[previousHeightIndex]; previousHeightIndex++; if(previousHeightIndex==list.length) // in case of stairs (no water collected) return coll; else previousHeight = list[previousHeightIndex]; } for(int i = previousHeightIndex; i<list.length; i++) { if(list[i] >= maxHeight) { // collect all temp water coll += temp; temp = 0; maxHeight = list[i]; // new max height } else { temp += maxHeight - list[i]; if(list[i] > previousHeight) { // we went up... collect some water int collWater = (i-previousHeightIndex)*(list[i]-previousHeight); coll += collWater; temp -= collWater; } } // previousHeight only changes if consecutive towers are not same height if(list[i] != previousHeight) { previousHeight = list[i]; previousHeightIndex = i; } } return coll; } 

Answer 11

我有一个解决scheme，只需要一个从左到右的遍历。

 def standing_water(heights): if len(heights) < 3: return 0 i = 0 # index used to iterate from left to right w = 0 # accumulator for the total amount of water while i < len(heights) - 1: target = i + 1 for j in range(i + 1, len(heights)): if heights[j] >= heights[i]: target = j break if heights[j] > heights[target]: target = j if target == i: return w surface = min(heights[i], heights[target]) i += 1 while i < target: w += surface - heights[i] i += 1 return w 

Answer 12

这是我在jQuery中的尝试。 它只能扫描到右侧。

工作小提琴（有帮助的日志logging）

 var a = [1, 5, 3, 7, 2]; var water = 0; $.each(a, function (key, i) { if (i > a[key + 1]) { //if next tower to right is bigger for (j = 1; j <= a.length - key; j++) { //number of remaining towers to the right if (a[key+1 + j] >= i) { //if any tower to the right is bigger for (k = 1; k < 1+j; k++) { //add to water: the difference of the first tower and each tower between the first tower and its bigger tower water += a[key] - a[key+k]; } } } } }); console.log("Water: "+water); 

Answer 13

这是我在Python中去的。 很确定它的工作原理，但没有testing它。

两个通过列表（但删除列表，因为它发现“水”）：

def答案（高地）：

 def accWater(lst,sumwater=0): x,takewater = 1,[] while x < len(lst): a,b = lst[x-1],lst[x] if takewater: if b < takewater[0]: takewater.append(b) x += 1 else: sumwater += sum(takewater[0]- z for z in takewater) del lst[:x] x = 1 takewater = [] else: if b < a: takewater.extend([a,b]) x += 1 else: x += 1 return [lst,sumwater] heights, swater = accWater(heights) x, allwater = accWater(heights[::-1],sumwater=swater) return allwater 

Answer 14

这个问题的一个直观的解决scheme是你根据左右边界的高度来限定问题并填充水。

我的解决scheme

• 从左侧开始，将这两个边界设置为第0个索引。
• 检查一下是否有某种轨迹 （如果你要在这些塔楼上行走，你会不会再往下走？）如果是这样的话，那么你find了一个正确的界限。
• 现在回来跟踪并填充水（我简单地把水添加到数组值本身，因为它使代码更清洁一些，但这显然不是必需的）。
• 冲突线：如果左边界塔的高度大于右边界塔的高度，则需要增加右边界。 原因是因为你可能会遇到更高的塔，需要补充更多的水。 但是，如果右塔高于左塔，那么在当前的子问题中不能再添加水。 因此，您将左边界移到右边界并继续。

这里是C＃中的一个实现：

  int[] towers = {1,5,3,7,2}; int currentMinimum = towers[0]; bool rightBoundFound = false; int i = 0; int leftBoundIndex = 0; int rightBoundIndex = 0; int waterAdded = 0; while(i < towers.Length - 1) { currentMinimum = towers[i]; if(towers[i] < currentMinimum) { currentMinimum = towers[i]; } if(towers[i + 1] > towers[i]) { rightBoundFound = true; rightBoundIndex = i + 1; } if (rightBoundFound) { for(int j = leftBoundIndex + 1; j < rightBoundIndex; j++) { int difference = 0; if(towers[leftBoundIndex] < towers[rightBoundIndex]) { difference = towers[leftBoundIndex] - towers[j]; } else if(towers[leftBoundIndex] > towers[rightBoundIndex]) { difference = towers[rightBoundIndex] - towers[j]; } else { difference = towers[rightBoundIndex] - towers[j]; } towers[j] += difference; waterAdded += difference; } if (towers[leftBoundIndex] > towers[rightBoundIndex]) { i = leftBoundIndex - 1; } else if (towers[rightBoundIndex] > towers[leftBoundIndex]) { leftBoundIndex = rightBoundIndex; i = rightBoundIndex - 1; } else { leftBoundIndex = rightBoundIndex; i = rightBoundIndex - 1; } rightBoundFound = false; } i++; } 

我毫不怀疑，有更多的最佳解决scheme。 我目前正在进行单程优化。 这个问题也有一个非常整洁的实现，它使用了一个类似的边界的概念。

Answer 15

这是我的解决scheme，它通过这个级别，很快，很容易理解这个想法是非常简单的：首先，你找出最大的高度（可能是多个最大值），然后你砍的景观分成3部分，从从最左边到最右边，从最右边到最后，最左边的最高高度。

在中间部分，很容易收集雨，一个for循环做到这一点。 然后，对于第一部分，您不断更新当前最大高度小于景观的最大高度。 一个循环做到这一点。 接下来的第三部分，你把你对第一部分做了什么

 def answer(heights): sumL = 0 sumM = 0 sumR = 0 L = len(heights) MV = max(heights) FI = heights.index(MV) LI = L - heights[::-1].index(MV) - 1 if LI-FI>1: for i in range(FI+1,LI): sumM = sumM + MV-heights[i] if FI>0: TM = heights[0] for i in range(1,FI): if heights[i]<= TM: sumL = sumL + TM-heights[i] else: TM = heights[i] if LI<(L-1): TM = heights[-1] for i in range(L-1,LI,-1): if heights[i]<= TM: sumL = sumL + TM-heights[i] else: TM = heights[i] return(sumL+sumM+sumR) 

Answer 16

这是一个在JAVA中遍历数字列表的解决scheme。 所以最坏的情况是O（n）。 （至less我是这么理解的）。

对于给定的参考编号，请继续查找大于或等于参考编号的编号。 保持这样做的数字，并将所有这些数字存储在一个列表中。

这个想法是这样的。 如果在6和9之间有5个数字，并且所有这五个数字都是0，则意味着在6和9之间可以存储总共30个单位的水。对于其间的数字不是0的实际情况，如果这些数字是0，我们只是从总量中扣除总数。（在这种情况下，我们从30中扣除）。 这将使这两座塔楼之间的水储备数量。 然后我们把这个数值保存在一个名为totalWaterRetained的variables中，然后从9之后的下一个塔开始，一直保持到最后一个元素为止。

添加totalWaterRetained的所有实例将给我们最终的答案。

JAVA解决scheme：（testing几个input。可能不是100％正确的）

 private static int solveLineTowerProblem(int[] inputArray) { int totalWaterContained = 0; int index; int currentIndex = 0; int countInBetween = 0; List<Integer> integerList = new ArrayList<Integer>(); if (inputArray.length < 3) { return totalWaterContained; } else { for (index = 1; index < inputArray.length - 1;) { countInBetween = 0; integerList.clear(); int tempIndex = index; boolean flag = false; while (inputArray[currentIndex] > inputArray[tempIndex] && tempIndex < inputArray.length - 1) { integerList.add(inputArray[tempIndex]); tempIndex++; countInBetween++; flag = true; } if (flag) { integerList.add(inputArray[index + countInBetween]); integerList.add(inputArray[index - 1]); int differnceBetweenHighest = min(integerList.get(integerList.size() - 2), integerList.get(integerList.size() - 1)); int totalCapacity = differnceBetweenHighest * countInBetween; totalWaterContained += totalCapacity - sum(integerList); } index += countInBetween + 1; currentIndex = index - 1; } } return totalWaterContained; } 

Answer 17

查找商店总水的JavaScript程序：

 let buildingHeights = [6, 1, 3, 5, 9, 2, 8]; /* * TOTAL store water * */ let max = (n1, n2) => { return n1 > n2 ? n1 : n2; }; let min = (n1, n2) => { return n1 > n2 ? n2 : n1; }; let maxHeightFromLeft = {}, maxHeightFromRight = {}; for (let i = 0; i < buildingHeights.length; i++) { maxHeightFromLeft[i] = max(buildingHeights[i], (i != 0) ? maxHeightFromLeft[i - 1] : 0); } for (let i = buildingHeights.length - 1; i >= 0; i--) { maxHeightFromRight[i] = max(buildingHeights[i], i < (buildingHeights.length - 1) ? maxHeightFromRight[i + 1] : 0); } let totalStorage = 0; for (let i = 0; i < buildingHeights.length; i++) { totalStorage += min(maxHeightFromLeft[i], maxHeightFromRight[i]) - buildingHeights[i]; } console.log(totalStorage); 

Answer 18

已经发布的17个答案中没有一个是真正时间最优的。

对于单个处理器，如许多人所指出的那样，2扫（ left->right ，接着right->left总和）是最佳的，但是使用多个处理器， 可以在O（log n ） 时间。 有很多方法可以做到这一点，所以我将解释一个与顺序algorithm非常接近的方法。

最大caching树O（log n）

1：创build所有塔楼的二叉树，使每个节点包含其任何孩子的最高塔楼的高度。 由于任何节点的两个叶子都可以独立计算，所以可以在O(log n)时间用n cpu来完成。

2a：然后，对于树中的每个节点，从根开始，让右叶具有值max(left, self, right) 。 这将在O(log n)时间使用n cpu创build从左到右的单调扫描。

2b：要计算从右到左的扫描，我们执行与以前相同的过程。 从max-cached树的根开始，让左边的叶子的值为max(left, self, right) 。 如果您愿意，可以并行执行从左到右（2a）和从右到左（2b）的扫描。 它们都使用max-cached树作为input，并且每个都生成一个新的树（或者如果你愿意，可以在原始树中设置它们自己的字段）。

3：然后，对于每个塔，其上的水量是min(ltr, rtl) - towerHeight ，其中ltr是我们之前做过的从左到右单调扫描的塔的值，我们左边的任何一个塔楼（包括我们自己）， rtl和右到左的扫描是一样的。

4：简单地用O(log n)时间树中的一棵树，使用n cpu's进行求和，就完成了。

---

¹如果现在的塔比我们左侧的所有塔高，或者比我们右侧的所有塔高， min(ltr, rtl) - towerHeight是零。

还有两种方法可以做到这一点 。

Answer 19

 private static int soln1(int[] a) { int ret=0; int l=a.length; int st,en=0; int h,i,j,k=0; int sm; for(h=0;h<l;h++) { for(i=1;i<l;i++) { if(a[i]<a[i-1]) { st=i; for(j=i;j<l-1;j++) { if(a[j]<=a[i] && a[j+1]>a[i]) { en=j; h=en; break; } } if(st<=en) { sm=a[st-1]; if(sm>a[en+1]) sm=a[en+1]; for(k=st;k<=en;k++) { ret+=sm-a[k]; a[k]=sm; } } } } } return ret; } 

Answer 20

这是我的问题，我用一个循环来看看以前的塔是否比实际的塔大。 如果是的话，我创build另一个循环来检查实际的塔楼是否大于或等于先前的塔楼。 如果是这样的话，我只是把之前塔和所有其他塔之间的所有高度差加起来。 如果没有，如果我的循环到达我的最后一个对象，那么我只是倒转arrays，以便前一个塔成为我的最后一个塔，并recursion调用我的方法。 那样的话，我肯定会find一个比我以前的塔更大的塔，并且会find正确的水量。

 public class towers { public static int waterLevel(int[] i) { int totalLevel = 0; for (int j = 1; j < i.length - 1; j++) { if (i[j - 1] > i[j]) { for (int k = j; k < i.length; k++) { if (i[k] >= i[j - 1]) { for (int l = j; l < k; l++) { totalLevel += (i[j - 1] - i[l]); } j = k; break; } if (k == i.length - 1) { int[] copy = Arrays.copyOfRange(i, j - 1, k + 1); int[] revcopy = reverse(copy); totalLevel += waterLevel(revcopy); } } } } return totalLevel; } public static int[] reverse(int[] i) { for (int j = 0; j < i.length / 2; j++) { int temp = i[j]; i[j] = i[i.length - j - 1]; i[i.length - j - 1] = temp; } return i; } public static void main(String[] args) { System.out.println(waterLevel(new int[] {1, 6, 3, 2, 2, 6})); } } 

Answer 21

列表中的第一个和最后一个酒吧不能陷阱水。 对于其余的塔楼，当最高高度向左和向右时，它们可以将水收集起来。

水的积累是：max（min（max_left，max_right） – current_height，0）

从左侧迭代，如果我们知道max_right更大，min（max_left，max_right）将变成max_left。 因此，积水简化为：max（max_left – current_height，0）从右侧考虑时，采用相同的模式。

从上面的信息，我们可以写出如下（在Python中）的O（N）时间和O（1）空间algorithm：

 def trap_water(A): water = 0 left, right = 1, len(A)-1 max_left, max_right = A[0], A[len(A)-1] while left <= right: if A[left] <= A[right]: max_left = max(A[left], max_left) water += max(max_left - A[left], 0) left += 1 else: max_right = max(A[right], max_right) water += max(max_right - A[right], 0) right -= 1 return water 

Answer 22

Euclid风格的替代algorithm，我认为比所有这些扫描更优雅：

把两座最高的塔作为左右塔。 这些塔楼之间的水量是显而易见的。

把下一个最高的塔join。 它必须在终塔之间，或者不在。 如果它位于末端塔之间，则它将取代塔体积的水量（感谢阿基米德的提示）。 如果在终塔外面，它将成为一个新的终塔，所含的附加水量是显而易见的。

重复下一个最高的塔，直到所有的塔都添加完毕。

我已经发布代码来实现这一点（在现代欧洲成语）： http : //www.rosettacode.org/wiki/Water_collected_between_towers#F.23

Answer 23

testing了所有提供的Java解决scheme，但是他们都没有通过我提出的一半testing用例，所以还有一个Java O（n）解决scheme ，涵盖了所有可能的情况。 该algorithm非常简单：

1）从头开始searchinput，search与给定塔相同或更高的塔，同时将下塔的可能水量总结为临时variables。

2）find塔后 – 将该临时variables添加到主结果variablesvar中，并缩短input列表。

3）如果没有更多的塔，然后倒转剩余的input，再次计算。

 public int calculate(List<Integer> input) { int result = doCalculation(input); Collections.reverse(input); result += doCalculation(input); return result; } private static int doCalculation(List<Integer> input) { List<Integer> copy = new ArrayList<>(input); int result = 0; for (ListIterator<Integer> iterator = input.listIterator(); iterator.hasNext(); ) { final int firstHill = iterator.next(); int tempResult = 0; int lowerHillsSize = 0; while (iterator.hasNext()) { final int nextHill = iterator.next(); if (nextHill >= firstHill) { iterator.previous(); result += tempResult; copy = copy.subList(lowerHillsSize + 1, copy.size()); break; } else { tempResult += firstHill - nextHill; lowerHillsSize++; } } } input.clear(); input.addAll(copy); return result; } 

对于testing用例，请看看这个testing课 。

如果发现未覆盖的testing用例，请随意创build一个请求请求）