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

2024.1.24力扣每日一题——美丽塔I

2024.1.24

      • 题目来源
      • 我的题解
        • 方法一 暴力枚举
        • 方法二 单调栈+前、后缀和

题目来源

力扣每日一题;题序:2865

我的题解

方法一 暴力枚举

将每个位置都作为山峰来进行遍历,计算每个山峰下的最大山脉数组和

时间复杂度:O( n 2 n^2 n2)
空间复杂度:O(1)

public long maximumSumOfHeights(List<Integer> maxHeights) {int n=maxHeights.size();long res=0;for(int i=0;i<n;i++){res=Math.max(res,getSum(maxHeights,i));}return res;
}
public long getSum(List<Integer> maxHeights,int index){long res=maxHeights.get(index);int t=maxHeights.get(index);for(int i=index-1;i>=0;i--){int cur=maxHeights.get(i);if(cur<=t){res+=cur;t=cur;}else{res+=t;}}t=maxHeights.get(index);for(int i=index+1;i<maxHeights.size();i++){int cur=maxHeights.get(i);if(cur<=t){res+=cur;t=cur;}else{res+=t;}}return res;
}
方法二 单调栈+前、后缀和

首先需要知道山状数组是会从山顶将数组分为两个部分,数组左侧构成非递减,数组右侧构成非递增。想要使得数组元素尽可能大,需要使得heights[i]取值为maxHeights[i],此时假设区间[0,i]构成的非递减元素和最大值为prefix[i],区间[i,n-1]构成的非递增数组元素和的最大值为suffix[i],则这时的山状数组的元素之和为:prefix[i]+suffic[i]-maxHeights[i]。减去maxHeights[i]是因为maxHeights[i]在左侧和右侧都被计算进去了,也就是计算了两次,所以需要减去一次。接下来分别讨论左侧和右侧的前缀和以及后缀和的计算:

  • 左侧的非递减(求前缀和):将maxHeights依次入栈,对于i位置元素来说,不断从栈顶弹出元素,直到栈中元素是一个非递减情况(也就是栈顶元素小于maxHeights[i])。假设栈顶元素为j位置元素,则对于i位置的最大前缀和:prefix[i]=prefix[j]+(i-j)*maxHeights[i]
  • 右侧的非递增(求后缀和):将maxHeights依次入栈,对于i位置元素来说,不断从栈顶弹出元素,直到栈中元素是一个非递减情况(也就是栈顶元素小于maxHeights[i])。假设栈顶元素为j位置元素,则对于i位置的最大前缀和:suffix[i]=suffix[j]+(j-i)*maxHeights[i]

所以最终的山状数组的最大值为:max(prefix[i]+suffic[i]-maxHeights[i])

时间复杂度:O(n)
空间复杂度:O(n)


有任何问题,欢迎评论区交流,欢迎评论区提供其它解题思路(代码),也可以点个赞支持一下作者哈😄~

相关文章:

2024.1.24力扣每日一题——美丽塔I

2024.1.24 题目来源我的题解方法一 暴力枚举方法二 单调栈前、后缀和 题目来源 力扣每日一题&#xff1b;题序&#xff1a;2865 我的题解 方法一 暴力枚举 将每个位置都作为山峰来进行遍历&#xff0c;计算每个山峰下的最大山脉数组和 时间复杂度&#xff1a;O( n 2 n^2 n2)…...

视频监控平台EasyCVR增加fMP4流媒体视频格式及其应用场景介绍

近期我们在视频监控管理平台EasyCVR系统中新增了HTTP-FMP4播放协议&#xff0c;今天我们就来聊聊该协议的特点和应用。 fMP4&#xff08;Fragmented MPEG-4&#xff09;是基于MPEG-4 Part 12的流媒体格式&#xff0c;是流媒体的一项重要技术&#xff0c;因为它能通过互联网传送…...

使用Python的pygame库实现迷宫游戏

使用Python的pygame库实现迷宫游戏 关于Python中pygame游戏模块的安装使用可见 https://blog.csdn.net/cnds123/article/details/119514520 先给出效果图&#xff1a; 这个游戏每次运行能自动随机生成迷宫布局。 在这个游戏中&#xff0c;玩家将使用键盘箭头键来移动&#x…...

Linux新手村必备!这些常用操作命令你掌握了吗?

在计算机的世界里&#xff0c;Linux操作系统以其强大的功能和灵活性受到了广大程序员和IT爱好者的喜爱。然而&#xff0c;对于初学者来说&#xff0c;Linux的操作命令可能会显得有些复杂和难以理解。 今天&#xff0c;我们就来一起探索一些Linux常用操作命令&#xff0c;让你的…...

ReactNative进阶(三十六):iPad横屏适配

文章目录 一、前言二、实现思路三、延伸阅读四、拓展阅读 一、前言 应用RN技术栈实现APP上线后&#xff0c;业务部门领导会上反馈未实现ipad横屏全屏展示&#xff0c;用户体验较差。由此&#xff0c;一场pad横屏全屏展示的APP调优工作由此开展。 二、实现思路 时间紧任务重&…...

jsx中使用插槽

1. jsx语法中使用插槽 以elementplus ElPopconfirm 为例 <el-popconfirm title"Are you sure to delete this?"><template #reference><el-button>Delete</el-button></template></el-popconfirm>使用 slots: {default: (dat…...

CentOS服务器拒绝SSH登录

当CentOS服务器拒绝SSH登录时&#xff0c;有几个可能的原因和解决方法&#xff1a; 检查网络连接&#xff1a;确保服务器与您的计算机之间的网络连接是正常的。您可以尝试使用其他网络连接或ping服务器以检查是否能够访问。 确认SSH服务正在运行&#xff1a;在服务器上确认SSH…...

React16源码: React中的completeUnitOfWork的源码实现

completeUnitOfWork 1 &#xff09;概述 各种不同类型组件的一个更新过程对应的是在执行 performUnitOfWork 里面的 beginWork 阶段它是去向下遍历一棵 fiber 树的一侧的子节点&#xff0c;然后遍历到叶子节点为止&#xff0c;以及 return 自己 child 的这种方式在 performUni…...

uniapp移动端——企业微信H5调用jssdk实现扫一扫,通过weixin-java-cp获取ticket签名,配置config

背景&#xff1a; 使用企业微信开发扫一扫功能 可信域名验证 (1)企业微信的可信域名需要和企业微信的备案主体一致。 域名备案主体可通过站长工具查看域名备案主体。https://icp.chinaz.com/ 企业微信备案主体可以咨询管理员 &#xff08;2&#xff09;通过nginx配置域名归…...

【前端基础--1】

为后面爬虫打基础 使用Visual Studio Code&#xff08;VS Code&#xff09; https://code.visualstudio.com/#alt-downloads 网页基础 创建一个html网页 新建一个文件 文件名后缀.html 书写网页模板 html:5 回车键&#xff08;或者Tab键&#xff09;英文感叹号! 回…...

E2 Mysql的基本操作和用户权限

一、实验目的: 要求掌握Mysql平台的基本操作和基本的权限管理。 二、实验要求: 1、基本硬件配置:英特尔Pentium III 以上,大于4G内存&#xff1b; 2、软件要求:Mysql&#xff1b; 3、时间:4小时&#xff1b; 4、撰写实验报告并按时提交。 三、实验内容: Group 1: 安装Mys…...

TCP 的三次握手和四次挥手

Java 面试题 TCP 三次握手 第一次握手&#xff1a;客户端向服务端发送SYN包。报文中标志位SYN1&#xff0c;序列号seqx&#xff08;x为随机整数&#xff09;。此时客户端进入了 SYN_SEND 同步已发送状态。 第二次握手&#xff1a;服务端回复客户端SYNACK包。报文中标志位SYN1&…...

mybatisplus做SQL拦截添加自定义排序

前言 工作中写的一段代码&#xff0c;备个份&#xff0c;以后兴许能直接用 功能描述&#xff1a;如果前端传入了排序规则&#xff0c;则优先按传入的字段进行排序&#xff0c;SQL原有的排序规则追加到末尾 注&#xff1a;我们项目里的分页查询&#xff0c;是基于XML的SQL执行的…...

代码随想录算法训练营第29天(回溯算法05 | * 491.递增子序列 * 46.全排列 * 47.全排列 II

回溯算法part05 491.递增子序列解题思路与 90.子集II 不同的点回溯三部曲 46.全排列解题思路遇到的难点思考 47.全排列 II解题思路注意点拓展需要加深理解的点&#xff08;需复习 小总结 491.递增子序列 本题和大家刚做过的90.子集II非常像&#xff0c;但又很不一样&#xff0c…...

mac docker desktop被禁用了,如何使用虚拟机lima运行docker

安装lima brew install lima创建配置 echo "\\ndynamic:\n big-sur:\n image: docker://docker:git\n linux:\n image: docker.io/limasoftware/ubuntu:20.04 \\n" > ~/.lima/default.yaml启动名叫default的虚拟机 limactl start default测试 limactl …...

sublime text 开启vim模式

sublime text 开启vim模式 打开配置文件 mac下点击菜单栏 Sublime Text -> Settings... -> Settings 修改配置文件并保存 添加配置 // 开启vim模式 "ignored_packages": [// "Vintage", ], // 以命令模式打开文件 "vintage_start_in_comman…...

JS词法结构

编程语言的词法结构是一套基础性规则&#xff0c;用来描述如何使用这门语言来编写程序。作为语法的基础&#xff0c;它规定了诸如变量名是什么样的、怎么写注释&#xff0c;以及程序语句之间如何分隔等规则。 2.1程序的文本 JS区分大小写 JS忽略程序记号&#xff08;token&am…...

程序媛的mac修炼手册-- 如何用Python节省WPS会员费

上篇分享了如何用微博爬虫&#xff0c;咱举例爬了女明星江疏影的微博数据。今天就用这些数据&#xff0c;给大家安利一下怎么用Python实现WPS中部分Excel付费功能。 MacOS系统自带的工具&#xff0c;绝大多数都非常顶&#xff0c;除Numbers外。当然&#xff0c;page比起word来&…...

ASP.NET Core NE8实现HTTP Upgrade和HTTP CONNECT代理服务器

看到一个文章[Go] 不到 100 行代码实现一个支持 CONNECT 动词的 HTTP 服务器 在NET8中如何实现 创建项目为MiniApi 编辑Program.cs文件。 var builder WebApplication.CreateSlimBuilder(args);var app builder.Build();// 将HTTP请求通过协议升级机制转为远程TCP请求&…...

apipost和curl收不到服务器响应的HTTP/1.1 404 Not Found

windows的apipost发送请求后&#xff0c;服务器响应了HTTP/1.1 404 Not Found&#xff0c;但是apipost一直显示发送中。 linux上的curl也一样。 使用wireshark抓包发现收到了响应&#xff0c;但是wireshark识别不了&#xff08;图中是回应404后关闭了连接&#xff09;&#xff…...

Android Wi-Fi 连接失败日志分析

1. Android wifi 关键日志总结 (1) Wi-Fi 断开 (CTRL-EVENT-DISCONNECTED reason3) 日志相关部分&#xff1a; 06-05 10:48:40.987 943 943 I wpa_supplicant: wlan0: CTRL-EVENT-DISCONNECTED bssid44:9b:c1:57:a8:90 reason3 locally_generated1解析&#xff1a; CTR…...

椭圆曲线密码学(ECC)

一、ECC算法概述 椭圆曲线密码学&#xff08;Elliptic Curve Cryptography&#xff09;是基于椭圆曲线数学理论的公钥密码系统&#xff0c;由Neal Koblitz和Victor Miller在1985年独立提出。相比RSA&#xff0c;ECC在相同安全强度下密钥更短&#xff08;256位ECC ≈ 3072位RSA…...

golang循环变量捕获问题​​

在 Go 语言中&#xff0c;当在循环中启动协程&#xff08;goroutine&#xff09;时&#xff0c;如果在协程闭包中直接引用循环变量&#xff0c;可能会遇到一个常见的陷阱 - ​​循环变量捕获问题​​。让我详细解释一下&#xff1a; 问题背景 看这个代码片段&#xff1a; fo…...

Redis相关知识总结(缓存雪崩,缓存穿透,缓存击穿,Redis实现分布式锁,如何保持数据库和缓存一致)

文章目录 1.什么是Redis&#xff1f;2.为什么要使用redis作为mysql的缓存&#xff1f;3.什么是缓存雪崩、缓存穿透、缓存击穿&#xff1f;3.1缓存雪崩3.1.1 大量缓存同时过期3.1.2 Redis宕机 3.2 缓存击穿3.3 缓存穿透3.4 总结 4. 数据库和缓存如何保持一致性5. Redis实现分布式…...

通过Wrangler CLI在worker中创建数据库和表

官方使用文档&#xff1a;Getting started Cloudflare D1 docs 创建数据库 在命令行中执行完成之后&#xff0c;会在本地和远程创建数据库&#xff1a; npx wranglerlatest d1 create prod-d1-tutorial 在cf中就可以看到数据库&#xff1a; 现在&#xff0c;您的Cloudfla…...

CMake基础:构建流程详解

目录 1.CMake构建过程的基本流程 2.CMake构建的具体步骤 2.1.创建构建目录 2.2.使用 CMake 生成构建文件 2.3.编译和构建 2.4.清理构建文件 2.5.重新配置和构建 3.跨平台构建示例 4.工具链与交叉编译 5.CMake构建后的项目结构解析 5.1.CMake构建后的目录结构 5.2.构…...

质量体系的重要

质量体系是为确保产品、服务或过程质量满足规定要求&#xff0c;由相互关联的要素构成的有机整体。其核心内容可归纳为以下五个方面&#xff1a; &#x1f3db;️ 一、组织架构与职责 质量体系明确组织内各部门、岗位的职责与权限&#xff0c;形成层级清晰的管理网络&#xf…...

VTK如何让部分单位不可见

最近遇到一个需求&#xff0c;需要让一个vtkDataSet中的部分单元不可见&#xff0c;查阅了一些资料大概有以下几种方式 1.通过颜色映射表来进行&#xff0c;是最正规的做法 vtkNew<vtkLookupTable> lut; //值为0不显示&#xff0c;主要是最后一个参数&#xff0c;透明度…...

Caliper 配置文件解析:config.yaml

Caliper 是一个区块链性能基准测试工具,用于评估不同区块链平台的性能。下面我将详细解释你提供的 fisco-bcos.json 文件结构,并说明它与 config.yaml 文件的关系。 fisco-bcos.json 文件解析 这个文件是针对 FISCO-BCOS 区块链网络的 Caliper 配置文件,主要包含以下几个部…...

Spring是如何解决Bean的循环依赖:三级缓存机制

1、什么是 Bean 的循环依赖 在 Spring框架中,Bean 的循环依赖是指多个 Bean 之间‌互相持有对方引用‌,形成闭环依赖关系的现象。 多个 Bean 的依赖关系构成环形链路,例如: 双向依赖:Bean A 依赖 Bean B,同时 Bean B 也依赖 Bean A(A↔B)。链条循环: Bean A → Bean…...