首页 > 其他分享 >42. 接雨水

42. 接雨水

时间:2023-06-13 14:55:28浏览次数:40  
标签:leftmax rightmax int 42 len height 雨水

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。

示例 1:


输入:height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出:6
解释:上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图,在这种情况下,可以接 6 个单位的雨水(蓝色部分表示雨水)。

> 双指针法

class Solution {
public:
    int trap(vector<int>& height) {
        int len = height.size();
        if(len <= 2) return 0;
        int sum = 0;
        vector<int> leftmax(len,0);
        vector<int> rightmax(len,0);
        leftmax[0] = height[0];
        rightmax[len-1] = height[len-1];
        for(int i = 1;i < len;i++){
            leftmax[i] = max(leftmax[i-1],height[i]);
        }
        for(int i = len-2;i >= 0;i--){
            rightmax[i] = max(rightmax[i+1],height[i]);
        }
        for(int i = 1;i < len-1;i++){
            int count = min(leftmax[i],rightmax[i]) - height[i];
            if(count > 0) sum += count;
        }
        return sum;
    }
};

> 单调栈



class Solution {
public:
    int trap(vector<int>& height) {
        //其实就是寻找下一个更高地势
        int len = height.size();
        if(len == 1) return 0;
        int sum = 0;
        stack<int> sta;
        sta.push(0);
        for(int i = 1;i < len;i++){
            int mid = sta.top();
            while(height[mid] <= height[i]){
                //出栈
                sta.pop();
                if(!sta.empty()){
                    int h = min(height[i],height[sta.top()]) - height[mid];
                    int w = i - sta.top() - 1;
                    sum += h*w;
                    mid = sta.top();
                }
                else{
                    break;
                }   
            }
            //入栈
            sta.push(i);
        }
        
        return sum;
    }
};

标签:leftmax,rightmax,int,42,len,height,雨水
From: https://www.cnblogs.com/lihaoxiang/p/17477511.html

相关文章

  • STM32F429 Discovery开发板应用:使用FreeRTOS队列+DMA双缓存实现串口数据接收
     参考帖子:https://blog.csdn.net/freedompoi/article/details/122350866目前想要实现STM32F4自带的DMA双缓冲区,尝试过一版,结果不能预期,就使用了RxHalfCplt和RxCplt去实现DMA双缓冲区的效果。现在有时间了,又重新实现STM32F4自带的DMA双缓冲区,作为参考。 MCU:STM32F429ZIT6......
  • 代码随想录算法训练营第五天| 242.有效的字母异位词 , 349. 两个数组的交集 , 202. 快
    242.有效的字母异位词 繁冗版:1,思路:先建立两个map,对应两个字符串对应的字符,同时对他们进行计数,如果这两个数字相等,那么就是相等2,代码1boolisAnagram_complicate(strings,stringt)2{3unordered_map<char,int>existedCharBys;45for(autoch......
  • Codeforces Beta Round #42 (Div. 2)-C. Lucky Tickets
    原题链接C.LuckyTicketstimelimitpertestmemorylimitpertestinputoutputVasyathinksthatluckyticketsaretheticketswhosenumbersaredivisibleby3.Hegathered......
  • LightOJ 1422 Halloween Costumes (区间DP)
    题意:你要连续去很多个舞会,给出n个舞会你需要穿的衣服的编号,一旦脱下就不能再穿,但是可以一件套一件,问最少需要准备多少件衣服。思路:区间DP,令dp[i][j]为第i到第j天需要的衣服,那么对于第i天,如果考虑后面没有和它重复的话,那么dp[i][j]=dp[i+1][j]+1,如果存在某一天a[i]==a[k],dp[i][j]=......
  • P1425 小鱼的游泳时间
    小鱼的游泳时间题目描述伦敦奥运会要到了,小鱼在拼命练习游泳准备参加游泳比赛,可怜的小鱼并不知道鱼类是不能参加人类的奥运会的。这一天,小鱼给自己的游泳时间做了精确的计时(本题中的计时都按小时制计算),它发现自己从时分一直游泳到当天的时分,请你帮小鱼计算一下,它这天一共......
  • 202306112142-《最近开发心得...》
     没有心得就是在瞎搞,写心得就是“埋头耕耕,抬头看看”,看看自己做了什么......    心得就是心的感受,并非得到了什么,我以前是搞前端开发,仅仅4-5年时间,见证Angular市场份额的减少,backbone还嫌有耳闻,鲜有招聘;React框架从耳闻到霸屏;个人沐浴jquery的春风,枯于市场类似Vue......
  • 第四天打卡|24. 两两交换链表中的节点 ● 19.删除链表的倒数第N个节点 面试题 02.07.
    24.两两交换链表中的节点:简单的交换 19.删除链表的倒数第N个节点: ●  面试题 02.07. 链表相交:这题没看过答案真的写不出来。太巧妙了  142.环形链表II:这题写过但是忘记怎么解的了还是看的答案。下次不能忘记  ......
  • sb+activiti7实例<二>20230424
    一、版本问题原Activiti的TijsRademakers团队去开发Flowable框架。现Activiti7是Salaboy团队开发的,内核使用的还是Activiti6,扩展了云化。Activiti5、Activiti6代码目前由Salaboy团队代为维护,目前官宣已经暂停维护  Activiti:Activiti在目前来看有点不思进取,核心功能和内核的优......
  • 代码随想录算法训练营第四天|24. 两两交换链表中的节点 , 19.删除链表的倒数第N个节点
    24.两两交换链表中的节点 个人感觉这个不太难,刚开始打算用步进值为2,来搞,但是没有想到链表应该是怎么样的,原来可以直接用: 1cur=cur->next->next 学到了,这是我自己写的代码:1ListNode*MyLinkedList::swapPairs(ListNode*head)2{3ListNode*dummyHead=new......
  • Python小屋刷题软件2425道题目分类速查表
    “Python小屋”编程比赛正式开始Python小屋刷题软件客户端使用说明(视频讲解)Python小屋刷题神器最近升级的新功能介绍每次录入新题目时都会更新下面的分类表,请注意查看最新信息。客观题分类:Python基础知识:1-57内置函数、运算符:58-320列表、元组、字典、集合、切片、推导式:321-792选......