当前位置: 首页 > news >正文

美丽塔O(n)解法单调栈

题目

见上一篇: 较难算法美丽塔时间复杂度O(n)-CSDN博客

时间复杂度

O(n)

分析

接着上篇。从左向右依次处理Left,处理Left[i]时,从右向左寻找第一个符合maxHeights[j]<maxHeights[i]的j。如果j1<j2,且maxHeights[j1]>=maxHeights[j2],那j1永远不会被选到。比如:{1,3,2,4,5},由于2在3右边,且小于3,则无论如何不会选中3。{1,2,2.....},后面无论有什么数,都不会选中第一个2,要么是其他数,要么是第二个2。
可以用栈实现,入栈maxHeights[i]之前,先出栈大于等于maxHeights[i]的数,剩余的都小于maxHeights[i]的数。也就是栈按升序排序的。由于maxHeights[i]和heights[i]都可以通过索引查询,栈中只需要记录索引。
Right类似,不再累赘。

样例分析

maxHeights

Left的栈情况

{1,2,3,4,5}

1

12

123

1234

12345

{5,4,3,2,1}

5

4

3

2

1

{1,2,4,3,5}

1

12

124

123

1235

{3,1,2}

3

1

12

{2,1,3}

2

1

13

代码

核心代码

class Solution {
public:long long maximumSumOfHeights(vector<int>& maxHeights) {m_c = maxHeights.size();m_vLeft.resize(m_c);m_vRight.resize(m_c);{//处理左边stack<int> sta;//记录做边的索引for (int i = 0; i < m_c; i++){const auto& h = maxHeights[i];while (sta.size() && (maxHeights[sta.top()] >= h)){sta.pop();//左边比右边大,不会被选中}if (sta.size()){m_vLeft[i] = m_vLeft[sta.top()] + (long long)h * (i - sta.top());}else{m_vLeft[i] =  (long long)h * (i -(-1) );}sta.emplace(i);}}{//处理右边stack<int> sta;//记录做边的索引for (int i = m_c - 1; i >= 0; i--){const auto& h = maxHeights[i];while (sta.size() && (maxHeights[sta.top()] >= h)){sta.pop();//左边比右边大,不会被选中}if (sta.size()){m_vRight[i] = m_vRight[sta.top()] + (long long)h * (sta.top()-i);}else{m_vRight[i] = (long long)h * (m_c-i);}sta.emplace(i);}}long long llRet = 0;for (int i = 0; i < m_c; i++){//假定i是山顶            long long llCur = m_vLeft[i] + m_vRight[i] - maxHeights[i];llRet = max(llRet, llCur);}return llRet;}int m_c;vector<long long> m_vLeft, m_vRight;
};

测试用代码

class CDebug : public Solution
{
public:
    long long maximumSumOfHeights(vector<long long>& maxHeights, vector<long long>& vLeft, vector<long long>& vRight)
    {
        vector<int> maxs(maxHeights.begin(), maxHeights.end());
        long long llRet = Solution::maximumSumOfHeights(maxs);
        for (int i = 0 ; i < vLeft.size();i++ )
        {
            assert(m_vLeft[i] == vLeft[i]);
            assert(m_vRight[i] == vRight[i]);
        }

        //调试用代码
        std::cout << "Left: ";
        for (int i = 0; i < m_c; i++)
        {
            std::cout << m_vLeft[i] << " ";
        }
        std::cout << std::endl;
        std::cout << "Right: ";
        for (int i = 0; i < m_c; i++)
        {
            std::cout << m_vRight[i] << " ";
        }
        std::cout << std::endl;
        return llRet;
    }
};
int main()
{
    vector < vector<vector<long long>>> param = { {{1,2,3,4,5} ,{1,3,6,10,15},{5,8,9,8,5}} ,
        {{5,4,3,2,1},{5,8,9,8,5},{15,10,6,3,1}} ,
        {{1,2,4,3,5},{1,3,7,9,14},{5,8,10,6,5}},
    {{3,1,2}, {3,2,4},{5,2,2}},
    {{2,1,3},{2,2,5},{4,2,3}},
        {{1000000000,1000000000,1000000000},{1000000000,2000000000,3000000000LL},{3000000000LL,2000000000,1000000000}} };
    for (auto& vv : param)
    {
        auto res = CDebug().maximumSumOfHeights(vv[0], vv[1], vv[2]);
    }
    //auto res = Solution().maxPalindromes("rire", 3);

//CConsole::Out(res);
}

测试环境

Win10,VS2022 C++17

下载

源码: 【免费】美丽塔单调栈O(n)解法资源-CSDN文库

doc 讲解排版好:【免费】闻缺陷则喜算法册(9月24增加美丽塔)资源-CSDN文库

相关文章:

美丽塔O(n)解法单调栈

题目 见上一篇&#xff1a; 较难算法美丽塔时间复杂度O(n)-CSDN博客 时间复杂度 O(n) 分析 接着上篇。从左向右依次处理Left&#xff0c;处理Left[i]时&#xff0c;从右向左寻找第一个符合maxHeights[j]<maxHeights[i]的j。如果j1<j2&#xff0c;且maxHeights[j1]&g…...

​的PDF文件压缩软件PDF Squeezer mac中文版​软件特点

PDF Squeezer mac是一款macOS平台上的PDF文件压缩软件&#xff0c;可以帮助用户快速地压缩PDF文件&#xff0c;从而减小文件大小&#xff0c;使其更容易共享、存储和传输。PDF Squeezer使用先进的压缩算法&#xff0c;可以在不影响文件质量的情况下减小文件大小。 PDF Squeezer…...

JS Ajax 封装

ajax 封装 一、 什么是Ajax&#xff1f;二、 Ajax的优缺点&#xff1f;2.1 优点2.2 缺点 三、 Ajax的使用3.1 状态码3.2 xhr的基本使用3.3 ajax原生封装&#xff1a;3.3.1 触发GET请求&#xff1a;3.3.2 调用POST请求&#xff1a; 四、Ajax的约束 一、 什么是Ajax&#xff1f; …...

观测云产品更新 | 优化日志数据转发、索引绑定、基础设施自定义等

观测云更新 日志 数据转发&#xff1a;新增外部存储转发规则数据查询&#xff1b;支持启用/禁用转发规则&#xff1b;绑定索引&#xff1a;日志易新增标签绑定&#xff0c;从而实现更细颗粒度的数据范围查询授权能力。 基础设施 > 自定义 【默认属性】这一概念更改为【必…...

trio ValueEvent

class AsyncValue(Generic[T]): 值包装器&#xff0c;提供等待值或过渡的能力。 概要&#xff1a; >>> a AsyncValue(0) # 注意&#xff1a;可以包装任何类型&#xff08;枚举&#xff0c;元组&#xff0c;...&#xff09; >>> ... >>> a.valu…...

js 新学一招,点击出现弹框,点击其他地方关闭弹框

文章目录 需求分析 需求 鼠标点击菜单&#xff0c;出现二级菜单&#xff0c;当点击其他地方时&#xff0c;二级菜单自动关闭 分析 <template><el-popoverv-model"visible"></el-popover> </template> <script> export default {dat…...

c#扩展包-Stateless

准备 Stateless是一个有限状态机扩展包。在c#项目中可以直接通过NuGet安装。 使用他需要先用枚举写好你所有可能的状态和子状态。 例如移动&#xff0c;下蹲&#xff0c;空闲&#xff0c;跳跃&#xff0c;游泳&#xff0c;奔跑&#xff0c;走路。 其中&#xff0c;奔跑和走路…...

Lua函数

--函数--无参无返回值 function F1()print("F1函数") end F1() print("*****************")--有参 function F2(a)print("F2函数"..a) end F2(2) --如果传入参数和函数数量不一致 --不会报错只是补空 F2(1,2) print("*****************&quo…...

左对齐和右对齐

%d默认为左对齐&#xff0c;%5d为左对齐&#xff08;以空格补齐&#xff09;&#xff0c;%05d为左对齐&#xff08;以0补齐&#xff09;&#xff0c;%-5d右补齐&#xff08;以空格补齐&#xff09;&#xff0c;整数和小数同理。%.xf,x为小数点后保留的位数。 #include<stdi…...

高仿互站网站源码 后台手机端两套模板 电脑端二十套模版

高仿互站网 后台手机端两套模板 电脑端二十套模版&#xff0c;简单介绍几个功能&#xff0c; 支持用户注册开店 开店申请&#xff0c;支持用户发布自己商品 支持卡密形式或实物形式&#xff0c; 支持用户自己发布求助 任务大厅功能&#xff0c;源码完整 更多功能自己去发现吧…...

Spring Controller内存马

获取当前上下文运行环境 getCurrentWebApplicationContext WebApplicationContext context ContextLoader.getCurrentWebApplicationContext(); 在SpringMVC环境下获取到的是一个XmlWebApplicationContext类型的Root WebApplicationContext&#xff1a; 在Spring MVC环境中…...

Mysql004:用户管理

前言&#xff1a;本章节讲解的是mysql中的用户管理&#xff0c;包括&#xff08;管理数据用户&#xff09;、&#xff08;控制数据库的访问权限&#xff09;。 目录 1. 查询用户 2. 创建用户 3. 修改用户密码 4. 删除用户 5. 权限控制 1. 查询用户 在mysql数据库中&#xff0…...

计算机视觉与深度学习 | 视觉里程计(Visual Odometry,VO)研究现状

===================================================== github:https://github.com/MichaelBeechan CSDN:https://blog.csdn.net/u011344545 ===================================================== 视觉里程计(Visual Odometry,VO) 研究背景及意义视觉里程计国内外研…...

Mojo:新型AI语言中的7个令人惊叹的Python升级,用简单的英语解释人工智能

Mojo&#xff1a;新型AI语言中的7个令人惊叹的Python升级 编程之美 用简单的英语解释人工智能 编程之美 由Coding Beauty设计的图像&#xff0c;使用Mojo标志和Python标志。 它比C更快&#xff0c;与Python一样简单&#xff0c;但速度提高了35000倍。 进入Mojo&#xff1a;一种…...

TCP连接的三次握手与四次挥手【重点】

TCP的运输连接管理概述 TCP是面向连接的协议&#xff0c;它基于运输连接来传送TCP报文段 TCP运输连接的建立和释放是每一次面向连接的通信中必不可少的过程 TCP运输连接有以下三个阶段 TCP的运输连接管理就是使运输连接的建立和释放都能正常的进行 TCP建立连接的三次握手&a…...

​重生奇迹MU新手玩家如何快速熟悉游戏​

新手玩家必须掌握什么呢&#xff0c;建议新手玩家去官方网站上面看看游戏的详细介绍&#xff0c;必须要好的熟悉游戏的各种玩法&#xff0c;让玩家可以有一个初步的认识。 所以这方面是非常重要的&#xff0c;建议每位重生奇迹MU玩家都应该注重这些东西。下面我们就来简单介绍…...

MySQL 用户权限和远程访问设置

目录 一、用户操作查看当前拥有用户创建用户修改用户密码删除用户给root用户开放外网访问 二、用户权限操作授予权限的原则查看授予用户的权限给用户添加权限回收权限 一、用户操作 先要使用root用户登录MySQL后在执行后面操作 查看当前拥有用户 SELECT host,user,Grant_pri…...

Golang基础之关键字

Type 参考 ## https://blog.csdn.net/SHELLCODE_8BIT/article/details/122837699 type有如下几种用法&#xff1a; 定义结构体定义接口类型定义类型别名类型查询 类型定义 type Celsius float64 // 摄氏温度 type Fahrenheit float64 // 华氏温度const (AbsoluteZeroC Cels…...

DataFrame插入多列PerformanceWarning: DataFrame is highly fragmented.

DataFrame插入多列PerformanceWarning: DataFrame is highly fragmented. dataframe列比较多&#xff0c;增加列的代码如下&#xff1a; dfpd.DataFrame() for i in range(1000):vlist[]for j in range(1000):vlist.append(j) df[COL_ str(i)] vlistdf警告错误&#x…...

Springboot登录验证的统一拦截处理

在进行Springboot项目开发的时候如何把每次请求都要验证的用户进行提取拦截统一处理 背景 如果不进行统一的拦截处理&#xff0c;其实这是一个非常痛苦的一件事情&#xff0c;因为每次用户请求你都要去进行用户的信息&#xff08;用户信息存储在session中&#xff09;的验证&…...

uniapp 对接腾讯云IM群组成员管理(增删改查)

UniApp 实战&#xff1a;腾讯云IM群组成员管理&#xff08;增删改查&#xff09; 一、前言 在社交类App开发中&#xff0c;群组成员管理是核心功能之一。本文将基于UniApp框架&#xff0c;结合腾讯云IM SDK&#xff0c;详细讲解如何实现群组成员的增删改查全流程。 权限校验…...

盘古信息PCB行业解决方案:以全域场景重构,激活智造新未来

一、破局&#xff1a;PCB行业的时代之问 在数字经济蓬勃发展的浪潮中&#xff0c;PCB&#xff08;印制电路板&#xff09;作为 “电子产品之母”&#xff0c;其重要性愈发凸显。随着 5G、人工智能等新兴技术的加速渗透&#xff0c;PCB行业面临着前所未有的挑战与机遇。产品迭代…...

(二)TensorRT-LLM | 模型导出(v0.20.0rc3)

0. 概述 上一节 对安装和使用有个基本介绍。根据这个 issue 的描述&#xff0c;后续 TensorRT-LLM 团队可能更专注于更新和维护 pytorch backend。但 tensorrt backend 作为先前一直开发的工作&#xff0c;其中包含了大量可以学习的地方。本文主要看看它导出模型的部分&#x…...

项目部署到Linux上时遇到的错误(Redis,MySQL,无法正确连接,地址占用问题)

Redis无法正确连接 在运行jar包时出现了这样的错误 查询得知问题核心在于Redis连接失败&#xff0c;具体原因是客户端发送了密码认证请求&#xff0c;但Redis服务器未设置密码 1.为Redis设置密码&#xff08;匹配客户端配置&#xff09; 步骤&#xff1a; 1&#xff09;.修…...

以光量子为例,详解量子获取方式

光量子技术获取量子比特可在室温下进行。该方式有望通过与名为硅光子学&#xff08;silicon photonics&#xff09;的光波导&#xff08;optical waveguide&#xff09;芯片制造技术和光纤等光通信技术相结合来实现量子计算机。量子力学中&#xff0c;光既是波又是粒子。光子本…...

Linux-进程间的通信

1、IPC&#xff1a; Inter Process Communication&#xff08;进程间通信&#xff09;&#xff1a; 由于每个进程在操作系统中有独立的地址空间&#xff0c;它们不能像线程那样直接访问彼此的内存&#xff0c;所以必须通过某种方式进行通信。 常见的 IPC 方式包括&#…...

表单设计器拖拽对象时添加属性

背景&#xff1a;因为项目需要。自写设计器。遇到的坑在此记录 使用的拖拽组件时vuedraggable。下面放上局部示例截图。 坑1。draggable标签在拖拽时可以获取到被拖拽的对象属性定义 要使用 :clone, 而不是clone。我想应该是因为draggable标签比较特。另外在使用**:clone时要将…...

简单介绍C++中 string与wstring

在C中&#xff0c;string和wstring是两种用于处理不同字符编码的字符串类型&#xff0c;分别基于char和wchar_t字符类型。以下是它们的详细说明和对比&#xff1a; 1. 基础定义 string 类型&#xff1a;std::string 字符类型&#xff1a;char&#xff08;通常为8位&#xff09…...

电脑定时关机工具推荐

软件介绍 本文介绍一款轻量级的电脑自动关机工具&#xff0c;无需安装&#xff0c;使用简单&#xff0c;可满足定时关机需求。 工具简介 这款关机助手是一款无需安装的小型软件&#xff0c;文件体积仅60KB&#xff0c;下载后可直接运行&#xff0c;无需复杂配置。 使用…...

SpringSecurity+vue通用权限系统

SpringSecurityvue通用权限系统 采用主流的技术栈实现&#xff0c;Mysql数据库&#xff0c;SpringBoot2Mybatis Plus后端&#xff0c;redis缓存&#xff0c;安全框架 SpringSecurity &#xff0c;Vue3.2Element Plus实现后台管理。基于JWT技术实现前后端分离。项目开发同时采 …...