接雨水、

简介:

@[toc]

接雨水(困难)

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

在这里插入图片描述
上面是由数组 [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

思路一

从底开始,一层一层往上算。
结果:超时

思路二

往上递归时,确保每次递归都有新值纪录
结果:超时

思路三

以栈形式,从左往右递归。
结果:通过

其实前两个思路都能通过绝大部分,只是最后一个测试样本有一万多个数据,我也是醉了。。。

我们可以不用像方法 2 那样存储最大高度,而是用栈来跟踪可能储水的最长的条形块。使用栈就可以在一次遍历内完成计算。

我们在遍历数组时维护一个栈。如果当前的条形块小于或等于栈顶的条形块,我们将条形块的索引入栈,意思是当前的条形块被栈中的前一个条形块界定。如果我们发现一个条形块长于栈顶,我们可以确定栈顶的条形块被当前条形块和栈的前一个条形块界定,因此我们可以弹出栈顶元素并且累加答案到 ans。

在这里插入图片描述

作者:LeetCode
链接: https://leetcode-cn.com/problems/trapping-rain-water/solution/jie-yu-shui-by-leetcode/ 来源:力扣(LeetCode) 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

代码实现:(思路2)

int onetrap(vector<int>& height, int begin, int end) {
        int area = 0;
        int min = height[begin];
        int flag = 0;
        //调整区间
        for (int j = begin; j <= end; j++) {
            if (height[j] == 0) {
                begin++;
            }
            else
                break;
        }
        for (int k = end; k >= begin; k--) {
            if (height[k] > 0) {
                end = k;
                break;
            }
        }

        if (begin >= end)
            return 0;

        //开始计数
        for (int i = begin; i <= end; i++) {
            if (height[i] == 0) {
                area++;
                flag++;
            }
            else {
                if (height[i] < min)
                    min = height[i];
            }
        }
        if (!flag) {
            for (int i = begin; i <= end; i++) {
                if (height[i] != 0) {
                    height[i] -= min;
                }
            }
        }
        else {
            for (int i = begin; i <= end; i++) {
                if (height[i] != 0) {
                    height[i] -= 1;
                }
            }
        }



        area += onetrap(height, begin, end);
        return area;
    }
    
    int trap(vector<int>& height) {
        if(height.size() == 0)
            return 0;
        return onetrap(height,0,height.size()-1);
    }

代码实现(思路3)

int trap(vector<int>& height) {
        int ans = 0;
        stack<int> st;
        for (int i = 0; i < height.size(); i++) {
            while(!st.empty() && height[st.top()] < height[i]) {
                int top = st.top();
                st.pop();
                if (st.empty()) break;
                int h = min(height[st.top()], height[i]) - height[top];
                int w = (i - st.top() - 1);
                ans += h * w;
            }
            st.push(i);
        }
        return ans;
    }
相关文章
|
1月前
|
人工智能 云栖大会
9.24-9.26,与魔搭,云栖见!
2025 杭州·云栖大会,来了!9月24日至26日,杭州·云栖小镇
78 0
|
11月前
|
机器学习/深度学习 人工智能 算法
小白教程-阿里云快速搭建Stable-Diffusion WebUI环境+免费试用
Stable-Diffusion 是目前热门的AIGC图像生成方案,通过开源与社区共享模型的方式,成为AI艺术与创意产业的重要工具。本文介绍通过阿里云快速搭建SD WebUI的服务,并有免费试用权益,适合新手入门。通过详细步骤指导,帮助读者轻松上手,享受创作乐趣。
1998 0
|
8月前
|
调度 vr&ar 图形学
【干货】实时云渲染与本地渲染的技术对比
实时渲染分为本地渲染和云渲染两种模式。随着XR技术在建筑、教育、医疗等领域的广泛应用,越来越多企业选择云渲染以提升效率、降低成本并增强协同能力。本文对比分析了这两种渲染模式的优劣,并重点介绍了实时云渲染方案具备便捷性、高效资源调度、超低时延网络、数据安全、终端轻量化及跨系统运行等优势,满足多种XR应用场景需求。
418 13
|
Web App开发 前端开发 JavaScript
Spring Boot整合 mybatisplus(后端) Vue+echarts+Element UI+axios(前端)---前后端项目实例demo
Spring Boot整合 mybatisplus(后端) Vue+echarts+Element UI+axios(前端)---前后端项目实例demo
595 1
|
11月前
|
计算机视觉
HDR的主要标准有哪些?
HDR(高动态范围)技术通过提供更广阔的亮度范围和丰富的色彩细节,显著提升图像质量,使电影、图片和游戏画面更加逼真。相比SDR,HDR拥有更宽的色域、更高的色深和动态范围,支持多种行业标准如HDR10、Dolby Vision、HDR10+、HLG和HDR Vivid,为用户带来更接近真实的视觉体验。
|
11月前
|
自然语言处理
从原理上总结chatGPT的Prompt的方法
从原理上总结chatGPT的Prompt的方法
148 0
|
机器学习/深度学习 编解码 算法
ADA-YOLO | YOLOv8+注意力+Adaptive Head,相对YOLOv8,mAP提升3%+118FPS
ADA-YOLO | YOLOv8+注意力+Adaptive Head,相对YOLOv8,mAP提升3%+118FPS
452 0
|
机器学习/深度学习 算法
分类预测 | MATLAB实现MIV-SVM的平均影响值MIV算法结合支持向量机分类预测
分类预测 | MATLAB实现MIV-SVM的平均影响值MIV算法结合支持向量机分类预测
阿里云服务器续费流程方法(简单2步搞定)
阿里云服务器怎么续费?续费流程方法图文详解
2052 1
阿里云服务器续费流程方法(简单2步搞定)