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

LC 2865. 美丽塔 I

2865. 美丽塔 I

难度 : 中等

题目大意

给你一个长度为 n 下标从 0 开始的整数数组 maxHeights

你的任务是在坐标轴上建 n 座塔。第 i 座塔的下标为 i ,高度为 heights[i]

如果以下条件满足,我们称这些塔是 美丽 的:

  1. 1 <= heights[i] <= maxHeights[i]
  2. heights 是一个 山脉 数组。

如果存在下标 i 满足以下条件,那么我们称数组 heights 是一个 山脉 数组:

  • 对于所有 0 < j <= i ,都有 heights[j - 1] <= heights[j]
  • 对于所有 i <= k < n - 1 ,都有 heights[k + 1] <= heights[k]

请你返回满足 美丽塔 要求的方案中,高度和的最大值

提示:

  • 1 <= n == maxHeights <= 10^3
  • 1 <= maxHeights[i] <= 10^9

示例 1:

输入:maxHeights = [5,3,4,1,1]
输出:13
解释:和最大的美丽塔方案为 heights = [5,3,3,1,1] ,这是一个美丽塔方案,因为:
- 1 <= heights[i] <= maxHeights[i]  
- heights 是个山脉数组,峰值在 i = 0 处。
13 是所有美丽塔方案中的最大高度和。

分析

根据数据范围可以知道时间复杂度要控制在 O ( n 2 l o g n ) O(n^2logn) O(n2logn),首先我们要确定这个山脉的中心,也就是说我们可以枚举这个中心,然后去构造这个山脉数组,至于怎么构造,因为确定了中心,所以我们可以枚举左右两边,以左边为例,我们要所得的山脉的高度之和最大,所以我们要尽可能取到最大的山脉高度,也就是说,如果当前山脉的最大高度小于等于右边山脉的高度,我们就可以直接取最大的高度,如果比右边的高度高,那么就只能取和右边的山脉相同的高度,右边是同理的,注意数据范围可能爆int,所以注意开long long

暴力枚举

class Solution {
public:using LL = long long;long long maximumSumOfHeights(vector<int>& maxHeights) {int n = maxHeights.size();LL res = 0;for (int i = 0; i < n; i ++){LL sum = maxHeights[i];LL t = maxHeights[i];// 用t表示当前山脉的限制高度for (int j = i - 1; j >= 0; j --)if (maxHeights[j] <= t) sum += maxHeights[j], t = maxHeights[j];else sum += t;t = maxHeights[i];for (int j = i + 1; j < n; j ++)if (maxHeights[j] <= t) sum += maxHeights[j], t = maxHeights[j];else sum += t;res = max(res, sum);}return res;}
};

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

分析

我们确定山峰之后,分析左边,从山峰往左看,根据上面的暴力做法的提示,我们发现,假设当前的山峰maxHeightx,那么如果左边的山脉是高于x的,左边的山脉就会受到限制,那么这个限制什么时候解除呢,碰到一个比x还要小的山脉,而且是第一个,那么我们就可以联想到单调栈的思想,我们可以存下标,我们首先找到受x限制的那一段,终点下标就是栈顶假设是t,那么这一段全部都是x高度,我们定义l[i]表示当前位置为山峰,从i往左看非递增的山脉的高度值和,假设l[i] = l[t] + (i - t) * x(下标从1开始),考虑边界情况,如果左边没有比x小的,那么左边都要受到限制,所以我们可以将栈底始终放一个下标0,这样就方便处理,至于右边的情况,是一样的,我们可以将数组反转一下,然后就是相同的处理

单调栈

class Solution {
public:using LL = long long;long long maximumSumOfHeights(vector<int>& maxHeights) {int n = maxHeights.size();vector<LL> l(n + 1), r(n + 1); // 下标从1开始方便处理边界auto f = [&](vector<LL>& g) {stack<LL> stk;stk.push(0); // 方便处理边界for (int i = 1; i <= n; i ++ ) {while (stk.size() > 1 && maxHeights[stk.top() - 1] >= maxHeights[i - 1]) stk.pop();g[i] = g[stk.top()] + (LL)(i - stk.top()) * maxHeights[i - 1];stk.push(i);}};f(l), reverse(maxHeights.begin(), maxHeights.end()), f(r);LL res = 0;for (int i = 1; i <= n; i ++) {res = max(res, l[i] + r[n - i + 1] - maxHeights[n - i]); // 注意此时数组已经反转了,所以下标要注意}return res;}
};

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

结束了

相关文章:

LC 2865. 美丽塔 I

2865. 美丽塔 I 难度 : 中等 题目大意 给你一个长度为 n 下标从 0 开始的整数数组 maxHeights 。 你的任务是在坐标轴上建 n 座塔。第 i 座塔的下标为 i &#xff0c;高度为 heights[i] 。 如果以下条件满足&#xff0c;我们称这些塔是 美丽 的&#xff1a; 1 < heights…...

代理设计模式JDK动态代理CGLIB动态代理原理

代理设计模式 代理模式&#xff08;Proxy&#xff09;&#xff0c;为其它对象提供一种代理以控制对这个对象的访问。如下图 从上面的类图可以看出&#xff0c;通过代理模式&#xff0c;客户端访问接口时的实例实际上是Proxy对象&#xff0c;Proxy对象持有RealSubject的引用&am…...

[陇剑杯 2021]webshell

[陇剑杯 2021]webshell 题目做法及思路解析&#xff08;个人分享&#xff09; 问一&#xff1a;单位网站被黑客挂马&#xff0c;请您从流量中分析出webshell&#xff0c;进行回答&#xff1a; 黑客登录系统使用的密码是_____________。 题目思路&#xff1a; 分析题目&…...

美易官方:小米汽车交付时间传闻被官方辟谣

在科技与互联网的快速发展浪潮中&#xff0c;各类信息传播速度之快令人咋舌。然而&#xff0c;信息的真实性却时常成为公众关注的焦点。近日&#xff0c;关于小米汽车交付时间的谣言再次引起市场的广泛关注。小米公司发言人迅速作出回应&#xff0c;明确指出这些关于小米汽车交…...

MySQL 简介

什么是MySQL&#xff1f;&#xff08;熟悉&#xff09; MySQL是一个开源的、使用标准SQL语言的、可运行于多个系统的、支持多语言的、支持大型数据库的关系型数据库管理系统。由瑞典 MySQL AB 公司开发&#xff0c;目前属于 Oracle 旗下产品。我们通常使用关系型数据库管理系统…...

动态规划最后一天(回文串)

目录 647. 回文子串 看到题目的第一想法 看到代码随想录之后的想法 自己实现过程中遇到的困难(看代码) 516.最长回文子序列 看到题目的第一想法 看到代码随想录之后的想法 自己实现过程中遇到的困难(看代码) 647. 回文子串 力扣题目链接…...

c语言之scanf函数

scanf函数语法格式与printf函数很相似&#xff0c;语法是scanf(格式控制,地址列表)组成 其中格式控制分为两部分&#xff0c;一部分由双引号括起来的&#xff0c;%和格式字符组成的格式字符串 普通字符串则是原样输出 地址列表是若干地址组成的表列&#xff0c;可以是变量的…...

ORM-02-JPA Java Persistence API 注解入门介绍

拓展阅读 The jdbc pool for java.(java 手写 jdbc 数据库连接池实现) The simple mybatis.&#xff08;手写简易版 mybatis&#xff09; JPA JPA是Java Persistence API的简称&#xff0c;中文名Java持久层API&#xff0c;是JDK 5.0注解或XML描述对象&#xff0d;关系表的映射…...

【MQ01】什么是消息队列?用哪个消息队列?

什么是消息队列&#xff1f;用哪个消息队列&#xff1f; 来了来了&#xff0c;消息队列系列总算来咯。对于搜索引擎相关的知识大家消化的怎么样呀&#xff1f;其实对于搜索引擎来说&#xff0c;我们学习的内容还是挺全面的&#xff0c;也算是比较深入了。而对于消息队列来说&am…...

2023年度AI盘点 AIGC|AGI|ChatGPT|人工智能大模型

前言 「作者主页」&#xff1a;雪碧有白泡泡 「个人网站」&#xff1a;雪碧的个人网站 2023年是人工智能大语言模型大爆发的一年&#xff0c;一些概念和英文缩写也在这一年里集中出现&#xff0c;很容易混淆&#xff0c;甚至把人搞懵。 文章目录 前言01 《ChatGPT 驱动软件开…...

【Flink-CDC】Flink CDC 介绍和原理概述

【Flink-CDC】Flink CDC 介绍和原理概述 1&#xff09;基于查询的 CDC 和基于日志的 CDC2&#xff09;Flink CDC3&#xff09;Flink CDC原理简述4&#xff09;基于 Flink SQL CDC 的数据同步方案实践4.1.案例 1 : Flink SQL CDC JDBC Connector4.2.案例 2 : CDC Streaming ETL…...

长城资产信息技术岗24届校招面试面经

本文介绍2024届秋招中&#xff0c;中国长城资产管理股份有限公司的信息技术岗岗位一面的面试基本情况、提问问题等。 10月投递了中国长城资产管理股份有限公司的信息技术岗岗位&#xff0c;所在部门为长城新盛信托有限责任公司。目前完成了一面&#xff0c;在这里记录一下一面经…...

【计算机网络】TCP握手与挥手:三步奏和四步曲

这里写目录标题 前言三次握手四次挥手三次握手和四次挥手的作用TCP三次握手的作用建立连接防止已失效的连接请求建立连接防止重复连接 TCP四次挥手的作用&#xff1a;安全关闭连接避免数据丢失避免半开连接 总结&#xff1a; 总结 前言 TCP&#xff08;传输控制协议&#xff09…...

设计模式学习总结

责任链模式 使用方法&#xff1a; 1.创建接口 2.定义实现类&#xff0c;每个实现类实现接口&#xff0c;并拥有一个ArchiveHandle的成员&#xff0c;用作责任链的链接 public interface ArchiveHandle {void handle(ArchiveVO archiveVO); } public class ArchivePreHandle i…...

「HDLBits题解」Cellular automata

本专栏的目的是分享可以通过HDLBits仿真的Verilog代码 以提供参考 各位可同时参考我的代码和官方题解代码 或许会有所收益 题目链接&#xff1a;Rule90 - HDLBits module top_module(input clk,input load,input [511:0] data,output [511:0] q );always (posedge clk) begin…...

什么是API ?

API&#xff08;应用程序编程接口&#xff09; 就像现成的家具套件相对于家居建设&#xff0c;用一些已经切好的木板组装一个书柜&#xff0c;显然比自己设计&#xff0c;寻找合适的木材&#xff0c;裁切至合适的尺寸和形状&#xff0c;找到正确尺寸的螺钉&#xff0c;然后再组…...

Pytest中conftest.py的用法

Pytest中conftest.py的用法 ​ 在官方文档中&#xff0c;描述conftest.py是一个本地插件的文件&#xff0c;简单的说就是在这个文件中编写的方法&#xff0c;可以在其他地方直接进行调用。 注意事项 只能在根目录编写conftest.py 插件加载顺序在搜集用例之前 基础用法 这里…...

java.lang.IllegalArgumentException: When allowCredentials is true

1.遇到的错误 java.lang.IllegalArgumentException: When allowCredentials is true, allowedOrigins cannot contain the special value "*" since that cannot be set on the "Access-Control-Allow-Origin" response header. To allow credentials to a…...

vue折叠展开transition动画使用keyframes实现

需求&#xff0c;我正常的菜单功能有隐藏与显示功能&#xff0c;需要增加动画 打开的时候宽度从0到300&#xff0c;关闭的时候&#xff0c;宽度从300到0 <template> <div id"app"> <button click"toggleLength">Toggle Length</bu…...

书生·浦语大模型实战营-学习笔记5

LMDeploy 大模型量化部署实践 大模型部署背景 LMDeploy简介 轻量化、推理引擎、服务 核心功能-量化 显存消耗变少了 大语言模型是典型的访存密集型任务&#xff0c;因为它是decoder-by-decoder 先把数据量化为INT4存起来&#xff0c;算的时候会反量化为FP16 AWQ算法&a…...

超短脉冲激光自聚焦效应

前言与目录 强激光引起自聚焦效应机理 超短脉冲激光在脆性材料内部加工时引起的自聚焦效应&#xff0c;这是一种非线性光学现象&#xff0c;主要涉及光学克尔效应和材料的非线性光学特性。 自聚焦效应可以产生局部的强光场&#xff0c;对材料产生非线性响应&#xff0c;可能…...

论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(二)

HoST框架核心实现方法详解 - 论文深度解读(第二部分) 《Learning Humanoid Standing-up Control across Diverse Postures》 系列文章: 论文深度解读 + 算法与代码分析(二) 作者机构: 上海AI Lab, 上海交通大学, 香港大学, 浙江大学, 香港中文大学 论文主题: 人形机器人…...

Java 语言特性(面试系列1)

一、面向对象编程 1. 封装&#xff08;Encapsulation&#xff09; 定义&#xff1a;将数据&#xff08;属性&#xff09;和操作数据的方法绑定在一起&#xff0c;通过访问控制符&#xff08;private、protected、public&#xff09;隐藏内部实现细节。示例&#xff1a; public …...

【入坑系列】TiDB 强制索引在不同库下不生效问题

文章目录 背景SQL 优化情况线上SQL运行情况分析怀疑1:执行计划绑定问题?尝试:SHOW WARNINGS 查看警告探索 TiDB 的 USE_INDEX 写法Hint 不生效问题排查解决参考背景 项目中使用 TiDB 数据库,并对 SQL 进行优化了,添加了强制索引。 UAT 环境已经生效,但 PROD 环境强制索…...

Vue3 + Element Plus + TypeScript中el-transfer穿梭框组件使用详解及示例

使用详解 Element Plus 的 el-transfer 组件是一个强大的穿梭框组件&#xff0c;常用于在两个集合之间进行数据转移&#xff0c;如权限分配、数据选择等场景。下面我将详细介绍其用法并提供一个完整示例。 核心特性与用法 基本属性 v-model&#xff1a;绑定右侧列表的值&…...

解锁数据库简洁之道:FastAPI与SQLModel实战指南

在构建现代Web应用程序时&#xff0c;与数据库的交互无疑是核心环节。虽然传统的数据库操作方式&#xff08;如直接编写SQL语句与psycopg2交互&#xff09;赋予了我们精细的控制权&#xff0c;但在面对日益复杂的业务逻辑和快速迭代的需求时&#xff0c;这种方式的开发效率和可…...

HTML 列表、表格、表单

1 列表标签 作用&#xff1a;布局内容排列整齐的区域 列表分类&#xff1a;无序列表、有序列表、定义列表。 例如&#xff1a; 1.1 无序列表 标签&#xff1a;ul 嵌套 li&#xff0c;ul是无序列表&#xff0c;li是列表条目。 注意事项&#xff1a; ul 标签里面只能包裹 li…...

cf2117E

原题链接&#xff1a;https://codeforces.com/contest/2117/problem/E 题目背景&#xff1a; 给定两个数组a,b&#xff0c;可以执行多次以下操作&#xff1a;选择 i (1 < i < n - 1)&#xff0c;并设置 或&#xff0c;也可以在执行上述操作前执行一次删除任意 和 。求…...

鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院查看报告小程序

一、开发环境准备 ​​工具安装​​&#xff1a; 下载安装DevEco Studio 4.0&#xff08;支持HarmonyOS 5&#xff09;配置HarmonyOS SDK 5.0确保Node.js版本≥14 ​​项目初始化​​&#xff1a; ohpm init harmony/hospital-report-app 二、核心功能模块实现 1. 报告列表…...

多种风格导航菜单 HTML 实现(附源码)

下面我将为您展示 6 种不同风格的导航菜单实现&#xff0c;每种都包含完整 HTML、CSS 和 JavaScript 代码。 1. 简约水平导航栏 <!DOCTYPE html> <html lang"zh-CN"> <head><meta charset"UTF-8"><meta name"viewport&qu…...