当前位置: 首页 > 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 维护条件类型...

爬虫基础学习day2

# 爬虫设计领域 工商&#xff1a;企查查、天眼查短视频&#xff1a;抖音、快手、西瓜 ---> 飞瓜电商&#xff1a;京东、淘宝、聚美优品、亚马逊 ---> 分析店铺经营决策标题、排名航空&#xff1a;抓取所有航空公司价格 ---> 去哪儿自媒体&#xff1a;采集自媒体数据进…...

自然语言处理——循环神经网络

自然语言处理——循环神经网络 循环神经网络应用到基于机器学习的自然语言处理任务序列到类别同步的序列到序列模式异步的序列到序列模式 参数学习和长程依赖问题基于门控的循环神经网络门控循环单元&#xff08;GRU&#xff09;长短期记忆神经网络&#xff08;LSTM&#xff09…...

在QWebEngineView上实现鼠标、触摸等事件捕获的解决方案

这个问题我看其他博主也写了&#xff0c;要么要会员、要么写的乱七八糟。这里我整理一下&#xff0c;把问题说清楚并且给出代码&#xff0c;拿去用就行&#xff0c;照着葫芦画瓢。 问题 在继承QWebEngineView后&#xff0c;重写mousePressEvent或event函数无法捕获鼠标按下事…...

uniapp手机号一键登录保姆级教程(包含前端和后端)

目录 前置条件创建uniapp项目并关联uniClound云空间开启一键登录模块并开通一键登录服务编写云函数并上传部署获取手机号流程(第一种) 前端直接调用云函数获取手机号&#xff08;第三种&#xff09;后台调用云函数获取手机号 错误码常见问题 前置条件 手机安装有sim卡手机开启…...

Redis:现代应用开发的高效内存数据存储利器

一、Redis的起源与发展 Redis最初由意大利程序员Salvatore Sanfilippo在2009年开发&#xff0c;其初衷是为了满足他自己的一个项目需求&#xff0c;即需要一个高性能的键值存储系统来解决传统数据库在高并发场景下的性能瓶颈。随着项目的开源&#xff0c;Redis凭借其简单易用、…...

LRU 缓存机制详解与实现(Java版) + 力扣解决

&#x1f4cc; LRU 缓存机制详解与实现&#xff08;Java版&#xff09; 一、&#x1f4d6; 问题背景 在日常开发中&#xff0c;我们经常会使用 缓存&#xff08;Cache&#xff09; 来提升性能。但由于内存有限&#xff0c;缓存不可能无限增长&#xff0c;于是需要策略决定&am…...

MacOS下Homebrew国内镜像加速指南(2025最新国内镜像加速)

macos brew国内镜像加速方法 brew install 加速formula.jws.json下载慢加速 &#x1f37a; 最新版brew安装慢到怀疑人生&#xff1f;别怕&#xff0c;教你轻松起飞&#xff01; 最近Homebrew更新至最新版&#xff0c;每次执行 brew 命令时都会自动从官方地址 https://formulae.…...

【Linux系统】Linux环境变量:系统配置的隐形指挥官

。# Linux系列 文章目录 前言一、环境变量的概念二、常见的环境变量三、环境变量特点及其相关指令3.1 环境变量的全局性3.2、环境变量的生命周期 四、环境变量的组织方式五、C语言对环境变量的操作5.1 设置环境变量&#xff1a;setenv5.2 删除环境变量:unsetenv5.3 遍历所有环境…...

Scrapy-Redis分布式爬虫架构的可扩展性与容错性增强:基于微服务与容器化的解决方案

在大数据时代&#xff0c;海量数据的采集与处理成为企业和研究机构获取信息的关键环节。Scrapy-Redis作为一种经典的分布式爬虫架构&#xff0c;在处理大规模数据抓取任务时展现出强大的能力。然而&#xff0c;随着业务规模的不断扩大和数据抓取需求的日益复杂&#xff0c;传统…...

【前端异常】JavaScript错误处理:分析 Uncaught (in promise) error

在前端开发中&#xff0c;JavaScript 异常是不可避免的。随着现代前端应用越来越多地使用异步操作&#xff08;如 Promise、async/await 等&#xff09;&#xff0c;开发者常常会遇到 Uncaught (in promise) error 错误。这个错误是由于未正确处理 Promise 的拒绝&#xff08;r…...