您现在的位置是:首页 > 正文

42. Trapping Rain Water 计算储水量

2024-04-01 00:54:22阅读 2
给定一个数组, 表示高度,计算存水量。
例子:
Input: [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6

方法1:动态规划

int trap(vector<int>& height) {
    if (height.empty()) { return 0; }
    
	int n = height.size();
	int left_max[n], right_max[n];
	
	left_max[0] = height[0];
	right_max[n - 1] = height[n - 1];
	
        for (int i = 1; i < n; ++i) {
	    left_max[i] = max(left_max[i - 1], height[i]);
	}

	for (int i = n - 2; i >= 0; --i) {
	    right_max[i] = max(right_max[i + 1], height[i]);
	}
	
	int res = 0;
	for (int i = 1; i < n - 1; ++i) {
            res += min(left_max[i], right_max[i]) - height[i];
	}
	return res;
}

方法2:使用栈

    int trap(vector<int>& height) {
        int waiter = 0;
        stack<int> s; // save idx

        for(int i = 0; i < height.size(); ++i) {
            while(!s.empty() && height[s.top()] < height[i]) {
                // 凹形计算waiter, (height[s.top()], height[mid], height[i])组成凹形
                int mid = s.top();
                s.pop();

                if(!s.empty()) {
                    waiter += (min(height[s.top()], height[i]) - height[mid]) * (i - s.top() - 1);
                }
            }
                
            s.push(i);
        }
        
        return waiter;
    }

方法3:双指针

int trap(vector<int>& height)
{
    int left = 0, right = height.size() - 1;
    int ans = 0;
    int left_max = 0, right_max = 0;
    while (left < right) {
        if (height[left] < height[right]) {
            height[left] >= left_max ? (left_max = height[left]) : ans += (left_max - height[left]);
            ++left;
        }
        else {
            height[right] >= right_max ? (right_max = height[right]) : ans += (right_max - height[right]);
            --right;
        }
    }
    return ans;
}
	

 

网站文章

  • 从订单信息页面进入订单详细商品页面,最简单的MVC思想

    从订单信息页面进入订单详细商品页面,最简单的MVC思想

    前言习惯上图,看流程图把,下面是具体实现以后的一个流程图。步骤- (1)点击订单详情,进入订单详情列表,展示订单的一下基本信息,在上图框内,可随机输入查询信息,查询具体订单信息。(2)点击订单商品详情,进入具体订单,图中进入订单编号1的商品页面,可以看到具体商品信息,从数据库我们建立一张表,关联订单跟具体商品的关系。正文直接上代码吧,简单粗暴,因为之前有

    2024-04-01 00:53:58
  • 使用C/C++实现Java的Native方法接口(JNI)(4)JNI数据类型

    在Java程序中使用native接口(JNI)调用外部的使用C/C++实现的函数

    2024-04-01 00:53:45
  • python学习笔记

    argparse模块1.使用步骤:(1)import argparse 首先导入模块(2)parser = argparse.ArgumentParser() 创建一个解析对象(3)parser.ad...

    2024-04-01 00:53:34
  • 基于Java的忘忧小区物业管理系统设计与实现

    基于Java的忘忧小区物业管理系统设计与实现

    我们通过对多个小区物业进行实地统计分析,了解具体的业务处理,准确的掌握了小区的服务业务体系,以便于我们开发一套完善的物业管理系统。随着互联网应用的普及,计算机已完全能够胜任物业管理工作,而且更加准确、...

    2024-04-01 00:53:25
  • ActiveMQ专题10 —— ActiveMQ的存储和持久化

    ActiveMQ专题10 —— ActiveMQ的存储和持久化

    官网click to 官网完美的诠释了持久化数据库问题体会一下面试redis持久化方式有几种AOF、RDB同样对于activemq,也是需要了解它的持久化机制持久化一句话就是:ActiveMQ宕机了,...

    2024-04-01 00:53:00
  • Cause: java.lang.IllegalArgumentException

    Cause: java.lang.IllegalArgumentException

    背景概述:在练习Mybatis整合Spring使用传统DAO模式开发,最后Junit测试时报了这样的错误“Cause: java.lang.IllegalArgumentException: Mapped Statements collection does not contain value for queryUserById”,很明显,我在测试“通过Id查询用户”这一 ...

    2024-04-01 00:52:49
  • LeetCode 4. 寻找两个正序数组的中位数(多解法)

    文章目录解法一:合并数组解法二:双指针解法三:二分解法三:进阶二分(划分数组) 解法一:合并数组 将两个数组合并后,直接根据下标找到中位数。时间复杂度O(m+n)O(m + n)O(m+n),空间复杂...

    2024-04-01 00:52:41
  • 趣学python算法一百例_DAY1

    趣学python算法一百例_DAY1

    一天应该1道,慢慢做 抓交通肇事犯 1.问题描述 一辆卡车违反交通规则,撞人后逃跑。现场有三人目击该事件,但都没有记住车号,只记下了车号的一些特征。甲说:牌照的前两位数字是相同的;乙说:牌照的后两位数...

    2024-04-01 00:52:14
  • 使用 Git,10个最需要常备的后悔药 热门推荐

    使用 Git,10个最需要常备的后悔药 热门推荐

    Git是目前世界上最优秀最流行的分布式版本控制系统,也是程序员们日常使用最频繁的工具之一(几乎每天都需要使用它来对源代码进行版本管理)。 使用Git的过程,难免由于手快或者别的什么原因,需要对做过的事...

    2024-04-01 00:52:07
  • 基础计算机教研室都上什么课,计算机教研室简介

    计算机教研室现有教授1人、副教授7人、讲师5人,是一支教学实力雄厚、业务素质高、科研能力强,团结友爱的教师团队。截止2021年4月,现有专职教师计算机教研室专职教师(5人): 高谨、翟哲、李宗峰、石沙...

    2024-04-01 00:52:00