题目1-头条雨水算法问题(2)

题目1-头条雨水算法问题(2)

题目参照:

头条雨水算法问题

第二种解法

感谢陈星涯同学提供了第二种思路,思路的图解如下:
second_method

思路:

操作分为以下几步:
1. 寻找最大值的位置。如图1所示。
2. 在最大值的左右侧,寻找第二大的值的位置。如图2所示。
3. 计算左第二大值到最大值和右第二大值到最大值之间能有多少个单位的水,如图3所示。
4. 分别以左第二大值和右第二大值为最大值,重复2,3,4步,直到计算到最左和最右的位置,如图4所示。

C++代码:

具体的C++代码如下所示

  1. 从左到右寻找最大值。

  1. 从右到左寻找最大值

  1. 计算最大值和第二大值之间能放多少个单位的水。

  1. 计算全部能放多少个单位的水。

  1. 主函数

除非注明,否则均为浮生笔记原创文章,转载必须以链接形式标明本文链接

本文链接:https://www.dennisthink.com/2019/01/27/246/

Leave a Reply

Your email address will not be published. Required fields are marked *