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

直方图中最大的矩形

#include<iostream>
#include<algorithm>

using namespace std;

const int N = 100010;

//l[i], r[i]表示第i个矩形的高度可向两侧扩展的左右边界
int h[N], q[N], l[N], r[N];

typedef long long LL;

int main()
{
    int n;
    while(scanf("%d", &n), n)
    {
        for(int i = 1; i <= n; i ++)  scanf("%d", &h[i]);
        h[0] = h[n + 1] = -1;

        int tt = -1;
        q[++ tt] = 0;
        for(int i = 1; i <= n; i ++)
        {
            while(h[q[tt]] >= h[i])  tt --;
            l[i] = i - q[tt];
            q[++ tt] = i;
        }

        tt = -1;
        q[++ tt] = n + 1;
        for(int i = n; i; i --)
        {
            while(h[q[tt]] >= h[i])  tt --;
            r[i] = q[tt] - i;
            q[++ tt] = i;
        }

        LL res = 0;
        for(int i = 1; i <= n; i ++)  res = max(res, (LL)h[i] * (l[i] + r[i] - 1));
        printf("%lld\n", res);
    }
    return 0;
}

相关文章:

直方图中最大的矩形

#include<iostream> #include<algorithm> using namespace std; const int N 100010; //l[i], r[i]表示第i个矩形的高度可向两侧扩展的左右边界 int h[N], q[N], l[N], r[N]; typedef long long LL; int main() { int n; while(scanf("%d"…...

分布式锁redisson

1&#xff1a;pom.xml添加依赖 <dependency><groupId>org.redisson</groupId><artifactId>redisson-spring-boot-starter</artifactId><version>3.21.1</version> </dependency>2-1&#xff1a;方法一&#xff1a;读取默认ym…...

将小爱音箱接入 ChatGPT 和豆包ai改造成专属语音助手

这个GitHub项目&#xff0c;mi-gpt&#xff0c;旨在将小爱音箱和米家设备与ChatGPT和豆包集成&#xff0c;有效地将这些设备转变为个性化语音助手。以下是对其功能和设置的详细分析&#xff1a; 主要特点 角色扮演&#xff1a;该项目允许小爱适应不同的角色&#xff0c;如伴侣…...

短网址生成原理及使用

生成短网址介绍&#xff1a; 一、定义 短网址&#xff08;Short URL&#xff09;是形式上比较短的网址&#xff0c;它通过将原始冗长的网址进行缩短&#xff0c;方便用户分享和记忆。短网址的生成主要依赖于特定的算法和服务&#xff0c;通过后端服务转向来实现网址的缩短。 …...

C#调用word组件转pdf,遇到视图保护解决方法

由于我们在自己项目里常常要调用office组件将word另存pdf格式&#xff0c;但是常遇到用户上传的word视图保护&#xff0c; 组件不能正常打开word而导致不能有效转pdf(原因是文件被WPS编辑过)&#xff0c;困扰很长时间&#xff0c;各种方法用过如用第三方组件替换office组件&…...

NAT端口映射,实现外网访问内网服务器

目录 前言一、搭建网络拓扑1.1 配置server和pc1.1.1 配置server01.1.2 配置server11.1.3 配置pc0 1.2 配置客户路由器1.2.1 配置路由器IP1.2.2 配置静态路由 1.3 配置ISP路由器 二、配置端口映射2.1 在客户路由器配置端口映射2.2 测试公网计算机访问私网服务器2.2.1 PC0向serve…...

【面试笔记】嵌入式软件工程师,汽车电子软件相关

文章目录 1. C语言基础1.1 const1.2 static1.3 回调函数的用法1.4 宏定义1.5 编译、链接过程1.6 堆与栈的区别&#xff1f;1.7 简单的字符串算法题&#xff0c;C语言实现1.7.1 给定一个字符串&#xff0c;按顺序筛选出不重复的字符组成字符串&#xff0c;输出该字符串1.7.2 给定…...

uniapp小程序开发 | 从零实现一款影视类app (后台接口实现,go-zero微服务的使用)

uniapp小程序开发实战系列&#xff0c;完整介绍从零实现一款影视类小程序。包含小程序前端和后台接口的全部完整实现。系列连载中&#xff0c;喜欢的可以点击收藏。 该篇着重介绍获取轮播图后台接口和获取正在热映电影的两个后台接口的实现。 后台服务使用golang&#xff0c;…...

【C#】委托

文章目录 委托自定义委托模板方法&#xff08;工厂模式回调(callback)函数&#xff08;观察者模式多播&#xff08;multicast&#xff09;委托委托的高级使用使用接口 重构 模板方法代码注意参考 委托 委托&#xff08;delegate&#xff09;是一种类型&#xff0c;定义了一种方…...

【面试题】创建两个线程交替打印100以内数字(一个打印偶数一个打印奇数)

阅读导航 一、问题概述二、解决思路三、代码实现四、代码优化 一、问题概述 面试官&#xff1a;C多线程了解吗&#xff1f;你给我写一下&#xff0c;起两个线程交替打印0~100的奇偶数。就是有两个线程&#xff0c;一个线程打印奇数另一个打印偶数&#xff0c;它们交替输出&…...

PgMP考试结束后多久出成绩?附成绩查询方法

PgMP考试结束后多久出成绩&#xff1f;这是许多参加PgMP考试的考生都非常关心的问题。今天就给大家讲解一下PgMP考试多久可以知道成绩&#xff1f; 一、PgMP考试成绩查询时间 PgMP考试一般在考试结束后的6-8周左右才会出成绩&#xff0c;届时PMI官方会通过电子邮件的形式提醒…...

springboot项目Redis统计在线用户

springboot项目Redis统计在线用户 我的项目有个显示用户的遗忘曲线&#xff0c;需要统计在线用户以计算他们的曲线 思考了两种方案&#xff0c;但都是用Redis的bitmap数据结构Bitmap是一种特殊类型的数组&#xff0c;其中每个元素只能存储0或1。在Redis中&#xff0c;Bitmap实际…...

GNeRF论文理解

文章目录 主要解决什么问题&#xff1f;结构设计以及为什么有效果&#xff1f;个人想法。 主要解决什么问题&#xff1f; 本文主要想要解决的问题是 如何使用uncalibrated的照片来进行Nerf重建。虽然说现在已经有了一些方式可以对相机位姿进行估计和优化&#xff0c;但是他们限…...

0531作业 链表

结果 整体代码 主要实现 /**实现* */ #include "./linklist.h"linklist* create_linklist(datatype param){linklist* node(linklist*)malloc(sizeof(linklist));if(NULLnode){puts("节点创建失败");}node->paramparam;node->pnextNULL;puts("…...

C++ STL - 容器

C STL&#xff08;标准模板库&#xff09;中的容器是一组通用的、可复用的数据结构&#xff0c;用于存储和管理不同类型的数据。 目录 零. 简介&#xff1a; 一 . vector&#xff08;动态数组&#xff09; 二. list&#xff08;双向链表&#xff09; 三. deque&#xff08…...

AI生成沉浸式3D世界(空间照片/视频)

面向Vision Pro等空间计算设备的产品指南 & 技术实现路径 一、通俗理解 ldi3格式概览:这是一种创新的3D内容格式,专为Vision Pro、Quest等VR头戴设备设计,让你能沉浸在一个几可乱真的三维世界,体验仿佛亲临其境的感受。 内容创作:利用开源工具,结合多角度摄像捕捉,…...

【Vue】异步更新 $nextTick

文章目录 一、引出问题二、解决方案三、代码实现 一、引出问题 需求 编辑标题, 编辑框自动聚焦 点击编辑&#xff0c;显示编辑框让编辑框&#xff0c;立刻获取焦点 即下图上面结构隐藏&#xff0c;下面结构显示&#xff0c;并且显示的时候让它自动聚焦。 代码如下 问题 “…...

【uCOS-III-编程指南】

uCOS-III-编程指南 ■ [野火]uCOS-III内核实现与应用开发实战指南■■■■ ■ [野火]uCOS-III内核实现与应用开发实战指南 添加链接描述 ■ ■ ■ ■...

2004NOIP普及组真题 2. 花生采摘

线上OJ&#xff1a; 【04NOIP普及组】花生采摘 核心思想&#xff1a; 1、本题为贪心即可。 2、因为本题严格限制了顺序&#xff0c;所以先把每个节点的花生数量按降序排序。然后逐一判断下一个花生是否需要去采摘即可 3、每一次采摘完&#xff0c;记录耗时 t 以及采集的花…...

SAP-SD-21-定义用于定价补充的定价过程

图9 维护条件类型...

逻辑回归:给不确定性划界的分类大师

想象你是一名医生。面对患者的检查报告&#xff08;肿瘤大小、血液指标&#xff09;&#xff0c;你需要做出一个**决定性判断**&#xff1a;恶性还是良性&#xff1f;这种“非黑即白”的抉择&#xff0c;正是**逻辑回归&#xff08;Logistic Regression&#xff09;** 的战场&a…...

练习(含atoi的模拟实现,自定义类型等练习)

一、结构体大小的计算及位段 &#xff08;结构体大小计算及位段 详解请看&#xff1a;自定义类型&#xff1a;结构体进阶-CSDN博客&#xff09; 1.在32位系统环境&#xff0c;编译选项为4字节对齐&#xff0c;那么sizeof(A)和sizeof(B)是多少&#xff1f; #pragma pack(4)st…...

Qt Widget类解析与代码注释

#include "widget.h" #include "ui_widget.h"Widget::Widget(QWidget *parent): QWidget(parent), ui(new Ui::Widget) {ui->setupUi(this); }Widget::~Widget() {delete ui; }//解释这串代码&#xff0c;写上注释 当然可以&#xff01;这段代码是 Qt …...

AtCoder 第409​场初级竞赛 A~E题解

A Conflict 【题目链接】 原题链接&#xff1a;A - Conflict 【考点】 枚举 【题目大意】 找到是否有两人都想要的物品。 【解析】 遍历两端字符串&#xff0c;只有在同时为 o 时输出 Yes 并结束程序&#xff0c;否则输出 No。 【难度】 GESP三级 【代码参考】 #i…...

【Redis技术进阶之路】「原理分析系列开篇」分析客户端和服务端网络诵信交互实现(服务端执行命令请求的过程 - 初始化服务器)

服务端执行命令请求的过程 【专栏简介】【技术大纲】【专栏目标】【目标人群】1. Redis爱好者与社区成员2. 后端开发和系统架构师3. 计算机专业的本科生及研究生 初始化服务器1. 初始化服务器状态结构初始化RedisServer变量 2. 加载相关系统配置和用户配置参数定制化配置参数案…...

前端导出带有合并单元格的列表

// 导出async function exportExcel(fileName "共识调整.xlsx") {// 所有数据const exportData await getAllMainData();// 表头内容let fitstTitleList [];const secondTitleList [];allColumns.value.forEach(column > {if (!column.children) {fitstTitleL…...

剑指offer20_链表中环的入口节点

链表中环的入口节点 给定一个链表&#xff0c;若其中包含环&#xff0c;则输出环的入口节点。 若其中不包含环&#xff0c;则输出null。 数据范围 节点 val 值取值范围 [ 1 , 1000 ] [1,1000] [1,1000]。 节点 val 值各不相同。 链表长度 [ 0 , 500 ] [0,500] [0,500]。 …...

Python如何给视频添加音频和字幕

在Python中&#xff0c;给视频添加音频和字幕可以使用电影文件处理库MoviePy和字幕处理库Subtitles。下面将详细介绍如何使用这些库来实现视频的音频和字幕添加&#xff0c;包括必要的代码示例和详细解释。 环境准备 在开始之前&#xff0c;需要安装以下Python库&#xff1a;…...

根据万维钢·精英日课6的内容,使用AI(2025)可以参考以下方法:

根据万维钢精英日课6的内容&#xff0c;使用AI&#xff08;2025&#xff09;可以参考以下方法&#xff1a; 四个洞见 模型已经比人聪明&#xff1a;以ChatGPT o3为代表的AI非常强大&#xff0c;能运用高级理论解释道理、引用最新学术论文&#xff0c;生成对顶尖科学家都有用的…...

Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决

Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决 问题背景 在一个基于 Spring Cloud Gateway WebFlux 构建的微服务项目中&#xff0c;新增了一个本地验证码接口 /code&#xff0c;使用函数式路由&#xff08;RouterFunction&#xff09;和 Hutool 的 Circle…...