100天iOS数据结构与算法实战 Day08 – 栈的算法实战 TrappingRainWater

题目描述

灵感示意图

思路：

 

• 看到这里是不是有点印象了，之前有关一个栈的算法。只不过这里的各种括号换成了bar，然后可以存储的水的坑就被每一对匹配bar夹着，所以我们只要找出每对匹配的bar并且计算相加即可。

 

• 我们用栈保存每堵墙。当遍历墙的高度的时候，如果当前高度小于栈顶的墙高度，说明这里会有积水，我们将墙的高度的下标入栈。

 

• 如果当前高度大于栈顶的墙的高度，说明之前的积水到这里停下，我们可以计算下有多少积水了。计算完，就把当前的墙继续入栈，作为新的积水的墙。

 

过程图

 

• 由于刚开始栈是空，所以将 height [ 0 ] 入栈。current 后移。

 

• 栈不为空，current指向的高度大于栈顶高度，所以栈顶元素 height [ 0 ] 出栈，栈现在是空则break跳出while循环体，height [ 1 ]入栈，current 后移。

 

• 由于 current 指向的高度小于栈顶高度，height [ 2 ] 入栈，current 后移。

 

 

• 由于栈不为空且current 指向的高度大于栈顶高度，栈顶 height [ 2 ] 出栈。计算 height [ 3 ] 和新的栈顶之间的水也就是蓝色的水。计算完之后继续判断 current 和新的栈顶的关系。

 

• current 指向的高度大于栈顶高度，栈顶 height [ 1 ] 出栈，由于栈空。所以把 height [ 3 ] 入栈。 current 后移。

 

• 由于 current 指向的高度小于栈顶 height [ 3 ] 的高度，height [ 4 ] 入栈。current 后移。

• 由于 current 指向的高度小于栈顶 height [ 4 ] 的高度，height [ 5 ] 入栈。current 后移。

 

• 由于 current 指向的高度大于栈顶 height [ 5 ] 的高度，将栈顶 height [ 5 ] 出栈，然后计算 current 指向的墙和新栈顶 height [ 4 ] 之间的水。

  

 

• 计算完之后继续判断 current 的指向和新栈顶的关系。此时 height [ 6 ] 不大于栈顶 height [ 4 ] ，所以将 height [ 6 ] 入栈。 current 后移。

 

• 由于 current 指向的高度大于栈顶高度，将栈顶 height [ 6 ] 出栈。计算和新的栈顶 height [ 4 ] 组成两个边界中的水。然后判断 current 和新的栈顶 height [ 4 ] 的关系，依旧是大于，所以把 height [ 4 ] 出栈。计算current 和 新的栈顶 height [ 3 ] 之间的水。

  

   

注意：其实不停的出栈，可以看做是在找与 7 匹配的墙，也就是 3 。

 

• 然后判断 current 和新的栈顶 height [ 3 ] 的关系，依旧是大于，所以把 height [ 3 ] 出栈，栈空。将 current 指向的 height [ 7 ] 入栈。current 后移。

 

• 后面的计算方式和前面几步类似。

 

代码

1. - (int)trapNSArray *)inputArray

2. {

3.    if (inputArray.count == 0)

4.    {

5.        return 0;

6.    }

7.  

8.    DSStack *newStack = [[DSStack alloc] initWithSize:15];

9.    int sumWater = 0, current = 0;

10.  

11.    while (current < inputArray.count)

12.    {

13.       //1

14.        while (![newStack isEmpty] && ([inputArray[current] intValue] > [inputArray[[[newStack peek] intValue]] intValue]))

15.        {

16.        //2

17.            int top = [[newStack peek] intValue];

18.            [newStack popLastObject];

19.            //3

20.            if ([newStack isEmpty])

21.            {

22.                break;

23.            }

24.            //4

25.            int distance = current - [[newStack peek] intValue] - 1;

26.  

27.            NSNumber *currentN = [NSNumber numberWithInt:[inputArray[current] intValue]];

28.  

29.            NSNumber *peekN = [NSNumber numberWithInt:[inputArray[[[newStack peek] intValue]] intValue]];

30.  

31.            NSNumber *minObj;

32.  

33.            NSComparisonResult r = [currentN compare:peekN];

34.            if (r == NSOrderedAscending)

35.            {

36.                minObj = currentN;

37.  

38.            }

39.            else if(r == NSOrderedSame)

40.            {

41.                minObj = currentN;

42.  

43.            }

44.            else if(r == NSOrderedDescending)

45.            {

46.                minObj = peekN;

47.            }

48.            //5

49.            int bounded_height = [minObj intValue] - [inputArray[top] intValue];

50.            //6

51.            sumWater += distance * bounded_height;

52.  

53.        }

54.      //7

55.        [newStack push:@(current++)];

56.    }

57.    return sumWater;

58.  

59. }

60.  

 

1. 如果当前栈是空且当前指向的高度大于栈顶高度就一直循环，否则到第7步current进栈，current后移。

2. 栈顶元素出栈，top就是后面计算水量要用到的。

3. 如果栈为空则跳出while循环，到第7步，current进栈，current后移。

4. 计算两个墙之间的距离。

5. 计算水量的高度。

6. 水量就=之前的水量+（距离*高度）。

交流群昵称：ios-Swift/Object C开发上架
交流群号： 869685378   找ios马甲包开发者合作，有兴趣请添加Q 51259559

• 100天iOS数据结构与算法实战 Day01

• 100天iOS数据结构与算法实战 Day02 – 栈

• 100天iOS数据结构与算法实战 Day03 – 栈的算法实战 Valid Parentheses

• 100天iOS数据结构与算法实战 Day04 – 栈的算法实战 逆波兰表示法

• 100天iOS数据结构与算法实战 Day05 – 栈的算法实战 Evaluate Reverse Polish Nota

• 100天iOS数据结构与算法实战 Day06 – 栈的算法实战 Simplify Path

• 100天iOS数据结构与算法实战 Day07 – 栈的算法实战 Min Stack