【LeetCode:2866. 美丽塔 II | 单调栈 + 前后缀数组】

在这里插入图片描述

🚀 算法题 🚀

🌲 算法刷题专栏 | 面试必备算法 | 面试高频算法 🍀
🌲 越难的东西,越要努力坚持,因为它具有很高的价值,算法就是这样✨
🌲 作者简介:硕风和炜,CSDN-Java领域新星创作者🏆,保研|国家奖学金|高中学习JAVA|大学完善JAVA开发技术栈|面试刷题|面经八股文|经验分享|好用的网站工具分享💎💎💎
🌲 恭喜你发现一枚宝藏博主,赶快收入囊中吧🌻
🌲 人生如棋,我愿为卒,行动虽慢,可谁曾见我后退一步?🎯🎯

🚀 算法题 🚀

在这里插入图片描述

在这里插入图片描述

🍔 目录

    • 🚩 题目链接
    • ⛲ 题目描述
    • 🌟 求解思路&实现代码&运行结果
      • ⚡ 单调栈 + 前后缀数组
        • 🥦 求解思路
        • 🥦 实现代码
        • 🥦 运行结果
    • 💬 共勉

🚩 题目链接

  • 2866. 美丽塔 II

⛲ 题目描述

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

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

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

1 <= heights[i] <= maxHeights[i]
heights 是一个 山脉 数组。
如果存在下标 i 满足以下条件,那么我们称数组 heights 是一个 山脉 数组:

对于所有 0 < j <= i ,都有 heights[j - 1] <= heights[j]
对于所有 i <= k < n - 1 ,都有 heights[k + 1] <= heights[k]
请你返回满足 美丽塔 要求的方案中,高度和的最大值 。

示例 1:

输入:maxHeights = [5,3,4,1,1]
输出:13
解释:和最大的美丽塔方案为 heights = [5,3,3,1,1] ,这是一个美丽塔方案,因为:

  • 1 <= heights[i] <= maxHeights[i]
  • heights 是个山脉数组,峰值在 i = 0 处。
    13 是所有美丽塔方案中的最大高度和。
    示例 2:

输入:maxHeights = [6,5,3,9,2,7]
输出:22
解释: 和最大的美丽塔方案为 heights = [3,3,3,9,2,2] ,这是一个美丽塔方案,因为:

  • 1 <= heights[i] <= maxHeights[i]
  • heights 是个山脉数组,峰值在 i = 3 处。
    22 是所有美丽塔方案中的最大高度和。
    示例 3:

输入:maxHeights = [3,2,5,5,2,3]
输出:18
解释:和最大的美丽塔方案为 heights = [2,2,5,5,2,2] ,这是一个美丽塔方案,因为:

  • 1 <= heights[i] <= maxHeights[i]
  • heights 是个山脉数组,最大值在 i = 2 处。
    注意,在这个方案中,i = 3 也是一个峰值。
    18 是所有美丽塔方案中的最大高度和。

提示:

1 <= n == maxHeights <= 105
1 <= maxHeights[i] <= 109

🌟 求解思路&实现代码&运行结果


⚡ 单调栈 + 前后缀数组

🥦 求解思路
  1. 美丽塔 I 给定的数据范围通过暴力就可以过掉,但是也不是说暴力就很简单。
  2. 该题目给定的数据范围更大了,无法通过前面的解法通过,所以,我们必须要在原来的基础上继续优化,优化掉重复计算的过程。
  3. 计算后缀,sum统计和,维护递增的单调栈,每次枚举山峰位置的时候,如果当前的高度是小于等于单调栈中栈顶的元素,此时将元素弹出,同时,将之前等于该位置元素的值都删除,sum -= (long)maxHeights.get(j) * (j - pre.peekLast())。弹出元素结束,此时更新元素的值,开始i添加,sum += (long)maxHeights.get(i) * (suf.peekLast() - i);,计算求解sum的数值,此时存到后缀数组当中去,并且将当前下标存储到栈中。继续迭代该过程。
  4. 前缀同理,最后循环遍历,找到ans = Math.max(ans, suffix[i + 1] + prefix[i]) 最大高度和。
  5. 实现代码如下所示:
🥦 实现代码
class Solution {
    public long maximumSumOfHeights(List<Integer> maxHeights) {
        int n = maxHeights.size();
        long[] suffix = new long[n + 1];
        Deque<Integer> suf = new LinkedList<>();
        suf.addLast(n);
        long sum = 0;
        for (int i = n - 1; i >= 0; i--) {
            int x = maxHeights.get(i);
            while (suf.size() > 1 && x <= maxHeights.get(suf.peekLast())) {
                int j = suf.pollLast();
                sum -= (long)maxHeights.get(j) * (suf.peekLast() - j);
            }
            sum += (long)maxHeights.get(i) * (suf.peekLast() - i);
            suffix[i] = sum;
            suf.addLast(i);
        }
        long[] prefix = new long[n + 1];
        Deque<Integer> pre = new LinkedList<>();
        pre.addLast(-1);
        sum = 0;
        for (int i = 0; i < n; i++) {
            int x = maxHeights.get(i);
            while (pre.size() > 1 && x <= maxHeights.get(pre.peekLast())) {
                int j = pre.pollLast();
                sum -= (long)maxHeights.get(j) * (j - pre.peekLast());
            }
            sum += (long)maxHeights.get(i) * (i - pre.peekLast());
            prefix[i] = sum;
            pre.addLast(i);
        }
        long ans = 0;
        for (int i = 0; i < n; i++) {
            ans = Math.max(ans, suffix[i + 1] + prefix[i]);
        }
        return ans;
    }
}
🥦 运行结果

在这里插入图片描述


💬 共勉

最后,我想和大家分享一句一直激励我的座右铭,希望可以与大家共勉!

在这里插入图片描述

在这里插入图片描述

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

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

相关文章

AI“百模大战”现状:向垂直、B端谋场景,算力仍是主要制约因素

文章目录 每日一句正能量前言AI&#xff08;人工智能&#xff09;大模型正“飞入”百姓家和行业中。向垂直、B端谋场景算力仍是主要制约因素构建“数据-模型-应用”飞轮后记 每日一句正能量 我们必须在失败中寻找胜利&#xff0c;在绝望中寻求希望。 前言 在当前快速发展的人工…

MACBOOK 通过iterm2连接堡垒机跳转服务器

本公司是通过齐治堡垒机连接远程服务器的环境&#xff0c;因为连接过程中需要自动输入密码和选择主机&#xff0c;所以要使用expect工具&#xff0c;编写expect脚本remote.exp #!/usr/bin/expectif { $argc ! 7 } {send_user "usage: expect $argv0 \[JUMP_HOST\] \[JUM…

基于Java+Springboot+Vue+elememt美食论坛平台设计实现

基于JavaSpringbootVueelememt美食论坛平台设计实现 &#x1f345; 作者主页 程序定制开发 &#x1f345; 欢迎点赞 &#x1f44d; 收藏 ⭐留言 &#x1f4dd; &#x1f345; 文末获取源码联系方式 &#x1f4dd; 文章目录 基于JavaSpringbootVueelememt美食论坛平台设计实现一…

【每日一题】移除石子使总数最小

文章目录 Tag题目来源解题思路方法一&#xff1a;贪心优先队列 写在最后 Tag 【贪心优先队列】【数组】【2023-12-23】 题目来源 1962. 移除石子使总数最小 解题思路 方法一&#xff1a;贪心优先队列 思路 本题比较简单&#xff0c;思路也十分清晰。对于 k 次操作&#xf…

[MTCTF 2022]easypickle

题目给了源码 import base64 import pickle from flask import Flask, session import os import randomapp Flask(__name__) app.config[SECRET_KEY] os.urandom(2).hex()app.route(/) def hello_world():if not session.get(user):session[user] .join(random.choices(&q…

乐吾乐大屏可视化前景和发展趋势

引言 在如今数智信息化时代&#xff0c;乐吾乐大屏可视化作为信息展示和决策支持的强大工具&#xff0c;正在迅速崛起&#xff0c;并在多个行业中发挥关键作用。本文将探讨乐吾乐大屏可视化的当前状态、未来前景以及发展趋势&#xff0c;以期为读者提供对这一技术的深入了解。 …

otter-harbor同步

一. 部署及依赖 otter Github (一). 服务启动 1. mysql 5.6版本以上&#xff0c;作为 otter-manger 使用的数据库 # mysql docker run --name mysql -p 3306:3306 -e MYSQL_ROOT_PASSWORD123456 -d mysql:5.7 --character-set-serverutf8mb4 --collation-serverutf8mb4_un…

抖店只能用官方电子面单?2024抖店玩法解读,附面单使用教程

我是王路飞。 正在做抖店的商家&#xff0c;应该都发现一件事情了&#xff0c;那就是现在的抖店好像不让拍单了&#xff0c;只能使用抖音的电子面单&#xff0c;打单发货。 说实话&#xff0c;这种情况已经出现过太多次了&#xff0c;导致很多商家不以为然。 我曾经也说过&a…

SpringBoot找不到或无法加载主类

1&#xff0c;bug贴图 2&#xff0c;问题说明 之所以导致这个问题是因为新建项目的时候&#xff0c;项目目录是这样的com.lab.hei.springboot.dubbo.ProviderApplication 我觉得这个目录太长了&#xff0c;所以修改了目录&#xff0c;修改后cn.alisa.springboot.dubbo.Provider…

hab_virtio hypervisor 虚拟化

Linux的 I / O 虚拟化 Virtio 框架 简而言之&#xff0c;virtio是半虚拟化管理程序中设备上的抽象层。virtio由Rusty Russell开发以支持他自己的虚拟化解决方案lguest。本文从准虚拟化和仿真设备的介绍开始&#xff0c;然后探讨的细节virtio。重点是virtio2.6.30内核发行版中的…

实在智能斩获钛媒体2023全球创新评选科技类「 大模型创新应用奖」

近日&#xff0c;历时三天的钛媒体2023 T-EDGE全球创新大会以“新视野新链接”为主题在北京隆重举办。作为科创领域全新高度的年度盛事&#xff0c;大会吸引了AI各产业链近百位海内外创投人、尖端企业家、商业领袖和国际嘉宾齐聚一堂&#xff0c;围绕新一轮AI革命、智慧数字化、…

LeetCode刷题--- 目标和

个人主页&#xff1a;元清加油_【C】,【C语言】,【数据结构与算法】-CSDN博客 个人专栏 力扣递归算法题 http://t.csdnimg.cn/yUl2I 【C】 http://t.csdnimg.cn/6AbpV 数据结构与算法 http://t.csdnimg.cn/hKh2l 前言&#xff1a;这个专栏主要讲述递归递归、搜…

论文配色(强烈推荐!!!)

目录 方案1&#xff08;复古&#xff09;&#xff1a; 方案2&#xff08;新特性&#xff09;&#xff1a; 方案3&#xff08;渐变&#xff09;&#xff1a; 方案4&#xff08;清新&#xff09;&#xff1a; 方案5&#xff08;怀旧&#xff09;&#xff1a; 方案6&#xf…

数据库管理-第126期 如何将数据从11g弄到19c上(202301223)

数据库管理-第126期 如何将数据从11g弄到19c上&#xff08;202301223&#xff09; 这应该是2023年写的最后一篇关于Oracle的文章吧&#xff0c;其实手上的Oracle数据库最近都挺平稳的&#xff0c;没啥素材&#xff0c;在JiekeXu徐小强老师的群里征集了一下内容&#xff0c;其中…

基于Java+SpringBoot+vue+element疫情物资捐赠分配系统设计和实现

基于JavaSpringBootvueelement疫情物资捐赠分配系统设计和实现 &#x1f345; 作者主页 系统定制开发 &#x1f345; 欢迎点赞 &#x1f44d; 收藏 ⭐留言 &#x1f4dd; &#x1f345; 文末获取源码联系方式 &#x1f4dd; 文章目录 基于JavaSpringBootvueelement疫情物资捐赠…

零基础制作宠物用品小程序

随着人们对宠物用品的需求不断增长&#xff0c;越来越多的人开始探索如何制作一个专业的宠物用品小程序。而乔拓云作为一款功能强大的在线商城制作工具&#xff0c;成为了许多商家的首选。本文将详细介绍如何使用乔拓云制作宠物用品小程序&#xff0c;让你轻松上手&#xff0c;…

「Verilog学习笔记」序列发生器

专栏前言 本专栏的内容主要是记录本人学习Verilog过程中的一些知识点&#xff0c;刷题网站用的是牛客网 timescale 1ns/1nsmodule sequence_generator(input clk,input rst_n,output reg data);reg [3:0] cnt ; integer num 11 ; always (posedge clk or negedge rst_n) beg…

pmp到底是什么?

一、PMP是什么 PMP 是项目管理的入门级证书&#xff0c;全称是项目管理专业人士资格认证&#xff0c;由美国项目管理协会&#xff08;PMI&#xff09;举办的&#xff0c;从1999 年到现在已经有20多年发展历史了。 顾名思义&#xff0c;PMP考试就是一场评估应试者是否具备专业…

鳄鱼目标检测数据集VOC格式100张

鳄鱼是一种生活在热带和亚热带地区的爬行动物&#xff0c;属于爬行纲鳄形目鳄鱼科。它们的体形庞大&#xff0c;有粗壮的四肢和强壮的尾巴&#xff0c;一般能长到2-6米长&#xff0c;体重可达500公斤以上。鳄鱼的皮肤粗糙&#xff0c;呈灰褐色或黑色&#xff0c;布满了坚韧的鳞…

目标检测应用场景—数据集【NO.24】行人车辆检测数据集2

写在前面&#xff1a;数据集对应应用场景&#xff0c;不同的应用场景有不同的检测难点以及对应改进方法&#xff0c;本系列整理汇总领域内的数据集&#xff0c;方便大家下载数据集&#xff0c;若无法下载可关注后私信领取。关注免费领取整理好的数据集资料&#xff01;今天分享…