算法实践——Twitter算法面试题(积水问题)的线性时间解法

简介: 问题描述:在下图里我们有不同高度的挡板。这个图片由一个整数数组所代表,数组中每个数是墙的高度。下图可以表示为数组(2、5、1、2、3、4、7、2)。假如开始下雨了,那么挡板之间的水坑能够装多少水(水足够多)呢?   下图是装满水的情况,一个蓝色格子代表一个单位的水。

问题描述:在下图里我们有不同高度的挡板。这个图片由一个整数数组所代表,数组中每个数是墙的高度。下图可以表示为数组(2、5、1、2、3、4、7、2)。假如开始下雨了,那么挡板之间的水坑能够装多少水(水足够多)呢?

Wall-1

 

下图是装满水的情况,一个蓝色格子代表一个单位的水。下图中一共装了10个单位的水。

Wall-2

 

 

问题分析:

 

先看看下图,判断哪个单元格的水能留下来。下图中的两个单元格,一个红色的单元格和一个绿色的单元格,哪个单元格的水是溜走了,哪个单元格的水能留下来?

Wall-3

很明显的,上图中的红色单元格的水会流走,绿色单元格的水会被留下来。

那么,仔细看看这两个单元格的区别在哪儿

区别就是,红色单元格只有右边的挡板比它高(不低于它),而绿色单元格左右两边都有挡板比它高(左边最高是5,右边最高是7)

这也就很好的理解了,如果水要能留下来,必须左右两边的挡板都比它高才行。(很明显的,不管哪一侧的挡板比水低,水就会朝哪个方向流出去)

 

于是,我给每个挡板定义了3个属性

V属性:本挡板的高度

L属性:本挡板左侧挡板的最高高度

R属性:本挡板右侧挡板的最高高度

 

那么,该挡板上方能积水的充要条件就是:L>V并且R>V

如果该挡板能积水,则积水量为:Min(L-V,R-V)

 

那么总的积水量就是所有挡板的积水量总和

 

问题就变成,如何求出每块挡板的L属性和R属性

用V、L、R三个数组标示挡板组的三个属性。一共有N块挡板,数组的下标从0到N-1。

V(i)表示第i块挡板的高度、L(i)表示第i块挡板的L属性、R(i)表示第i块挡板的R属性

可知的是L(0)=0,R(N-1)=0;

 

不失一般性,考虑第i块挡板的L属性(i>0)。L(i-1)表示第i-1块挡板的L属性。那么,可知

如果L(i-1)>V(i-1),则L(i)=L(i-1)

如果L(i-1)≤V(i-1),则L(i)=V(i-1)

综上所述:L(i)=Max(L(i-1),V(i-1))(i>0)

同理可述:R(i)=Max(R(i+1),V(i+1))(i<N-1)

 

而由于L(0)=0,R(N-1)=0。则说明第0、N块挡板(最左和最右的挡板)是不会积水的

因此,计算L和R的属性以及计算积水量的下标从1开始到N-2即可

 

代码如下:

Public Class clsFillWater
    Public Shared Function FillWater2(ByVal ParamArray Nums() As Integer) As Integer
        Dim L(Nums.Length - 1) As Integer
        Dim R(Nums.Length - 1) As Integer
        Dim I As Integer
        Dim Result As Integer = 0

 

        If Nums.Length < 3 Then Return 0

 

        L(0) = 0
        R(Nums.Length - 1) = 0

        For I = 1 To Nums.Length - 2
            L(I) = Math.Max(L(I - 1), Nums(I - 1))
            R(Nums.Length - 1 - I) = Math.Max(R(Nums.Length - I), Nums(Nums.Length - I))
        Next

 

        For I = 1 To Nums.Length - 2
            If L(I) > Nums(I) AndAlso R(I) > Nums(I) Then
                Result += Math.Min(L(I), R(I)) - Nums(I)
            End If
        Next

        Return Result
    End Function
End Class

 

从代码看,该算法的时间效率是O(N)的,是线性时间的。在文章 Twitter算法面试题详解(Java实现) 的评论中也有一个线性时间的算法(效率相当,可能还优于本算法),不过理解上不如这个简单明了。

相关文章
|
存储 缓存 网络协议
Linux环境下配置虚拟ip,方法1:新增多个子网卡,每个子网卡有独立的配置文件
Linux环境下配置虚拟ip,方法1:新增多个子网卡,每个子网卡有独立的配置文件
6825 0
Linux环境下配置虚拟ip,方法1:新增多个子网卡,每个子网卡有独立的配置文件
|
5月前
|
运维 监控 前端开发
一个运维人的“断舍离”:我如何用不到30MB的 MSRM3 替换掉了桌面上的六个工具
本文讲述一位资深运维人从多工具切换的疲惫,到遇见轻量、开箱即用的MSRM3监控平台的心路历程。它仅30MB单文件、免依赖、跨平台,集成IP定位、全能工具箱与零代码大屏,让运维回归问题本身——工具隐形,效率可见。(239字)
|
5月前
|
数据采集 XML SQL
一文搞懂提示工程、RAG、微调——LLM应用开发的三个层次
本文直击LLM应用落地痛点,厘清提示工程、RAG与微调的本质差异与适用边界:提示工程管“怎么问”,RAG解“问什么”,微调改“模型认知”。拒绝盲目微调,倡导分层诊断、闭环迭代,助你少走弯路、高效落地。
|
消息中间件 Linux RocketMQ
【RocketMq】RocketMq 4.9.4 Windows-docker 部署
【RocketMq】RocketMq 4.9.4 Windows-docker 部署
1226 0
【RocketMq】RocketMq 4.9.4 Windows-docker 部署
|
7月前
|
人工智能 自然语言处理 运维
OpenClaw是什么?使用OpenClaw龙虾AI助手能干什么?
OpenClaw(龙虾)是阿里云推出的开源AI智能体,不止聊天,更能自动办公、写代码、管日程、控家居、整知识库等。零门槛一键部署,支持多端使用,让AI真正帮你干活。(239字)
|
11月前
|
JSON JavaScript 数据可视化
TinyEngine物料自动导入上手指南:从零搭建高效低代码开发环境
本文介绍如何通过TinyEngine物料自动导入工具提升低代码开发效率。涵盖环境配置、物料规范、自动化脚本开发、Git集成及CI/CD实践,手把手教你实现物料一键导入与版本管理,助力团队高效协作。
|
6月前
|
弹性计算 人工智能 关系型数据库
阿里云轻量应用服务器秒杀活动解析:用户关心的秒杀时间、活动对象与规则、策略等问题都在这
2026年阿里云轻量应用服务器秒杀活动全新升级,新增2核4G配置,价格低至9.9元/月或199元/年,同时保留2核2G配置38元/年的优惠。活动每日10点、15点准时开抢,限阿里云新用户参与。轻量应用服务器预装了丰富镜像,可快速搭建网站和应用,其中2核4G配置默认预装OpenClaw,便于搭建AI助理。若秒杀未果,用户可选择非秒杀优惠价或转向“低价长效特惠”的云服务器ECS。
|
人工智能 编解码 自然语言处理
VideoMind:Chain-of-LoRA突破时间盲区让AI真正看懂长视频
VideoMind是一种新型视频语言代理,专为解决长视频时间定位理解挑战设计。它通过“Chain-of-LoRA”技术结合四个专业角色(Planner、Grounder、Verifier、Answerer)实现高效推理。Planner分析查询并制定计划;Grounder精确定位视频时刻;Verifier验证候选时刻准确性;Answerer生成最终答案。此架构在14个公共基准上表现出色,尤其在长视频定位任务中超越了现有模型,同时保持高内存效率。VideoMind推动了多模态AI的发展,提供了解决复杂视频理解问题的新方法。
11222 5
|
计算机视觉
RT-DETR改进策略【卷积层】| CGblock 内容引导网络 利用不同层次信息,提高多类别分类能力 (含二次创新)
RT-DETR改进策略【卷积层】| CGblock 内容引导网络 利用不同层次信息,提高多类别分类能力 (含二次创新)
458 5
RT-DETR改进策略【卷积层】| CGblock 内容引导网络 利用不同层次信息,提高多类别分类能力 (含二次创新)
|
Python
使用python合并文档
使用python合并文档
532 0