欢迎关注
最酷最in的云资讯

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


题目描述

1.png

灵感示意图

2.png

思路:


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


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


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


过程图


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

3.png


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

4.png


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


5.png


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

6.png


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

7.png

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

8.png

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

9.png


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

    33.png


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

22.png

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

    11.png

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


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

44.png


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


代码

  1. - (int)trap🙁NSArray *)inputArray

  2. {

  3.    if (inputArray.count == 0)

  4.    {

  5.        return 0;

  6.    }


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

  8.    int sumWater = 0, current = 0;


  9.    while (current < inputArray.count)

  10.    {

  11.       //1

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

  13.        {

  14.        //2

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

  16.            [newStack popLastObject];

  17.            //3

  18.            if ([newStack isEmpty])

  19.            {

  20.                break;

  21.            }

  22.            //4

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


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


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


  26.            NSNumber *minObj;


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

  28.            if (r == NSOrderedAscending)

  29.            {

  30.                minObj = currentN;


  31.            }

  32.            else if(r == NSOrderedSame)

  33.            {

  34.                minObj = currentN;


  35.            }

  36.            else if(r == NSOrderedDescending)

  37.            {

  38.                minObj = peekN;

  39.            }

  40.            //5

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

  42.            //6

  43.            sumWater += distance * bounded_height;


  44.        }

  45.      //7

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

  47.    }

  48.    return sumWater;


  49. }



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

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

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

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

  5. 计算水量的高度。

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

GitHubDemo地址

GitHubDemo

References

[1] GithubDemo: https://github.com/renmoqiqi/100-Days-Of-iOS-DataStructure-Algorithm/tree/master/Day08

转载自公众号:人魔七七

  • 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

赞(0) 打赏
未经允许不得转载:云微资讯 » 100天iOS数据结构与算法实战 Day08 – 栈的算法实战 TrappingRainWater
分享到: 更多 (0)

云微资讯 科技新媒体资讯平台

关于我们联系我们

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏