代码随想录训练营Day 63|力扣42. 接雨水、84.柱状图中最大的矩形

1.接雨水

代码随想录

代码:(单调栈)

class Solution {
public:
    int trap(vector<int>& height) {
        int result = 0;
        stack<int> st;
        st.push(0);
        for(int i = 1; i < height.size(); i++){
            if(height[i] < height[st.top()]){
                st.push(i);
            }else if(height[i] == height[st.top()]){
                st.pop(); // 元素值相等留一个就好了,避免重复计算。不过这句话删了也可以
                st.push(i);
            }else{
                while(!st.empty() && height[i] > height[st.top()]){
                    int mid = st.top();
                    st.pop(); // 这里有了pop操作就要注意让栈不为空时再操作
                    if(!st.empty()){
                        int h = min(height[i],height[st.top()]) - height[mid];
                        int w = i - st.top() - 1;
                        result += h * w;
                    }
                }
                st.push(i);
            }
        }
        return result;
    }
};

思路:(这里是横着求矩形面积的)

其实就是找每个元素前面第一个比它大的值(就是单调栈里的栈顶元素的下一个值),和后面第一个比它大的值(用单调栈,第一次比栈顶元素大的当前遍历的元素值)。

矩形的高=这两个值高度的最小值-当前计算的元素高度

矩形的宽=后面元素下标值-前面元素的下标值-1

注意:单调栈里存的都是下标。

2.柱状图中最大的矩形

 代码随想录

代码: (单调栈)

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int result = 0;
        stack<int> st;
        heights.insert(heights.begin(),0);
        heights.push_back(0);
        // 向数组首位位置加0,为了避免 因为数组本身就单调 而出现 没有走到计算面积的步骤
        st.push(0);
        for(int i = 1; i < heights.size(); i++){
            if(heights[i] > heights[st.top()]){
                st.push(i);
            }else if(heights[i] == heights[st.top()]){
                st.pop();
                st.push(i);
            }else{
                while(!st.empty() && heights[i] < heights[st.top()]){
                    int h = heights[st.top()];
                    st.pop();
                    if(!st.empty()){
                        int w = i - st.top() - 1;
                        int sum = w * h;
                        result = max(result,sum);
                    }
                }
                st.push(i);
            }
        }
        return result;
    }
};

思路:

和接雨水的区别就是,这里用的是递减栈,以及需要在数组首末补0

基于每一个高度,求左右两边最邻近的比它高度小的元素。

矩形的高=当前计算的元素高度

矩形的宽=后面元素下标值-前面元素的下标值-1

首先来说末尾为什么要加元素0?

如果数组本身就是升序的,例如[2,4,6,8],那么入栈之后 都是单调递减,一直都没有走 情况三 计算结果的哪一步,所以最后输出的就是0了。

开头为什么要加元素0?

如果数组本身是降序的,例如 [8,6,4,2],在 8 入栈后,6 开始与8 进行比较,此时我们得到 mid(8),rigt(6),但是得不到 left。

(mid、left,right 都是对应版本一里的逻辑)

因为 将 8 弹出之后,栈里没有元素了,那么为了避免空栈取值,直接跳过了计算结果的逻辑。

之后又将6 加入栈(此时8已经弹出了),然后 就是 4 与 栈口元素 8 进行比较,周而复始,那么计算的最后结果resutl就是0

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/728026.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

【02】区块链技术应用

区块链在金融、能源、医疗、贸易、支付结算、证券等众多领域有着广泛的应用&#xff0c;但是金融依旧是区块链最大且最为重要的应用领域。 1. 区块链技术在金融领域的应用 1.2 概况 自2019年以来&#xff0c;国家互联网信息办公室已发布八批境内区块链信息服务案例清单&#…

IT人周末兼职跑外面三个月心得分享

IT人周末兼职跑外面三个月心得分享 这四个月来&#xff0c;利用周末的时间兼职跑外面&#xff0c;总共完成了564单&#xff0c;跑了1252公里&#xff0c;等级也到了荣耀1&#xff0c;周末不跑就会减分。虽然收入只有3507.4元。 - 每一次的接单&#xff0c;每一段路程&#xff…

8.12 矢量图层面要素单一符号使用四(线符号填充)

文章目录 前言线符号填充&#xff08;Line pattern fill&#xff09;QGis设置面符号为线符号填充&#xff08;Line pattern fill&#xff09;二次开发代码实现线符号填充&#xff08;Line pattern fill&#xff09; 总结 前言 本章介绍矢量图层线要素单一符号中使用线符号填充…

Day 44 Ansible自动化运维

Ansible自动化运维 几种常用运维工具比较 ​ Puppet ​ —基于 Ruby 开发,采用 C/S 架构,扩展性强,基于 SSL,远程命令执行相对较弱ruby ​ SaltStack ​ —基于 Python 开发,采用 C/S 架构,相对 puppet 更轻量级,配置语法使用 YAML,使得配置脚本更简单 ​ Ansible ​ —基于 …

基于MATLAB的误码率与信噪比(附完整代码与分析)

目录 一. 写在前面 二. 如何计算误码率 三. 带噪声的误码率分析 3.1 代码思路 3.2 MATLAB源代码及分析 四. 总结 4.1 输入参数 4.2 规定比特长度 4.3 特殊形式比较 一. 写在前面 &#xff08;1&#xff09;本文章主要讨论如何仿真误码率随着信噪比变化的图像 &#…

Hi3861 OpenHarmony嵌入式应用入门--0.96寸液晶屏 iic驱动ssd1306

使用iic驱动ssd1306&#xff0c;代码来源hihope\hispark_pegasus\demo\12_ssd1306 本样例提供了一个HarmonyOS IoT硬件接口的SSD1306 OLED屏驱动库&#xff0c;其功能如下&#xff1a; 内置了128*64 bit的内存缓冲区&#xff0c;支持全屏刷新;优化了屏幕刷新速率&#xff0c;…

Unity URP简单烘焙场景步骤

Unity URP简单烘焙场景步骤 前言项目场景布置灯光模型Lighting设置环境设置烘焙前烘焙后增加角色 前言 项目中要烘焙一个3D场景&#xff0c;用的URP渲染管线&#xff0c;简单记录一下。 项目 场景布置 灯光 因为场景中有能动的东西&#xff0c;需要一部分实时光照&#xf…

SAP BC OBB8 自解释字段50个字符加到100个字符的长度

开整 SE11 复制TEXT1_052 -> ZTEXT1_052 并把域 改成TEXT100 se11 修改T052 激活 报错了&#xff0c;是个视图的问题 参考 SAP COEP V_COEP列不一致的问题及处理_sap coep表报错-CSDN博客 更新一下 再激活成功了 但是OBB8 保存的还是50个字符长度 &#xff0c;中…

Diffusion 扩散模型(DDPM)

Diffusion 扩散模型&#xff08;DDPM&#xff09; 一、什么是扩散模型&#xff1f; 随着Stable Diffusion 3的问世&#xff0c;AI绘画再次成为最为火热的AI方向之一&#xff0c;那么不可避免地再次会问到Stable Diffusion里的这个”Diffusion”到底是什么&#xff1f;其实扩散…

maxKb配置ollama,API域名无效

要修改 ollama 的配置文件&#xff0c;以允许所有 IP 访问&#xff0c;请按照以下步骤进行操作&#xff1a; 编辑 /etc/systemd/system/ollama.service 文件&#xff1a; sudo nano /etc/systemd/system/ollama.service在 [Service] 部分添加一行&#xff1a; [Unit] Descripti…

随机森林算法详解

随机森林算法详解 随机森林&#xff08;Random Forest&#xff09;是一种集成学习方法&#xff0c;通过构建多个决策树并将它们的预测结果结合起来&#xff0c;来提高模型的准确性和稳定性。随机森林在分类和回归任务中都表现出色&#xff0c;广泛应用于各类机器学习问题。本文…

C++ 计算凸包点的最小旋转矩形

RotateRect.h #include <vector>/** * brief 计算点集最小旋转外接矩形 */ class RotateRect { public:enum { CALIPERS_MAXHEIGHT 0, CALIPERS_MINAREARECT 1, CALIPERS_MAXDIST 2 };struct Point {float x, y;};using Points std::vector<Point>;struct Size…

FlinkCDC 3.1.0 与 Flink 1.18.0 安装及使用 Mysql To Doris 整库同步,使用 pipepline连接器

cd flink-cdc-3.1.0 bin/flink-cdc.sh 会用到 linux的系统环境变量&#xff08;vim /etc/profile配置&#xff09;&#xff0c;使用环境变量 FLINK_HOME flinkcdc & flink 安装及使用&#xff1a; 1、flink-cdc-3.1.0/lib/ 内容如下&#xff1a; 2、flink-cdc-3.1.0/mysql…

硅谷裸机云服务器:定义、特点与应用

硅谷&#xff0c;作为全球科技创新的重镇&#xff0c;一直是科技领域的风向标。近年来&#xff0c;随着云计算技术的飞速发展&#xff0c;硅谷的科技公司们也在不断探索和创新&#xff0c;以满足日益增长的计算需求。其中&#xff0c;裸机云服务器作为一种新兴的计算资源交付方…

新手下白对Latex下手啦!

第一次使用latex&#xff0c;浅浅地记录一下子吧。 首先我们一般会下载一个latex模板&#xff0c;如果想知道咋下载&#xff0c;评论去告诉俺哟&#xff01; 新手小白首先要看懂结构&#xff0c;不然完全下不了手&#xff0c;本文就以IEEE的模板&#xff0c;从头往下讲咯~ 第…

【代码随想录】【算法训练营】【第44天】 [322]零钱兑换 [279]完全平方数 [139]单词拆分

前言 思路及算法思维&#xff0c;指路 代码随想录。 题目来自 LeetCode。 day 44&#xff0c;周四&#xff0c;坚持不住了~ 题目详情 [322] 零钱兑换 题目描述 322 零钱兑换 解题思路 前提&#xff1a; 思路&#xff1a; 重点&#xff1a; 代码实现 C语言 [279] 完全…

7亿中国男人,今年夏天都在穿什么?

文丨郭梦仪 北京气温已经逼近38度&#xff0c;注重防晒的人群中这次多了男人的身影。 程序员宇宙中心&#xff0c;清河万象汇西区&#xff0c;小米su7吸引众多男士前来观摩&#xff0c;和对面蕉下门店里的“防晒衣大军”恰好呼应上了。 北京清河万象汇的防晒衣专卖店 夏日将…

Studying-代码随想录训练营day15| 222.完全二叉树的节点个数、110.平衡二叉树、257.二叉树的所有路径、404.左叶子之和

第十五天&#xff0c;二叉树part03&#x1f4aa;&#xff0c;编程语言&#xff1a;C 目录 257.完全二叉树的节点个数 110.平衡二叉树 257.二叉树的所有路径 404.左叶子之和 总结 257.完全二叉树的节点个数 文档讲解&#xff1a;代码随想录完全二叉树的节点个数 视频讲解…

118 杨辉三角

题目 给定一个非负整数 numRows&#xff0c;生成「杨辉三角」的前 numRows 行。 在「杨辉三角」中&#xff0c;每个数是它左上方和右上方的数的和。 示例 输入: numRows 5 输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]] 解析 就是模拟法&#xff0c;没有什么特殊的…

从仓位出发 略谈在线伦敦银交易的技巧

现在我们做伦敦银投资&#xff0c;都是通过线上完成的。在线做伦敦金交易的意思&#xff0c;就是投资者通过网络&#xff0c;在PC端或者移动端去利用交易软件完成交易&#xff0c;那么在线伦敦银交易有什么技巧呢&#xff1f;下面我们就从仓位的角度来讨论。 投资者入场后所持有…