LeetCode每日一题[C++]-1793.好子数组的最大分数

2024-03-19 09:52

本文主要是介绍LeetCode每日一题[C++]-1793.好子数组的最大分数,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目描述

给你一个整数数组 nums (下标从 0 开始)和一个整数 k 。

一个子数组 (i, j) 的 分数 定义为 min(nums[i], nums[i+1], ..., nums[j]) * (j - i + 1) 。一个  子数组的两个端点下标需要满足 i <= k <= j 。

请你返回  子数组的最大可能 分数 。

示例 1:

输入:nums = [1,4,3,7,4,5], k = 3
输出:15
解释:最优子数组的左右端点下标是 (1, 5) ,分数为 min(4,3,7,4,5) * (5-1+1) = 3 * 5 = 15 。

示例 2:

输入:nums = [5,5,4,5,4,1,1,1], k = 0
输出:20
解释:最优子数组的左右端点下标是 (0, 4) ,分数为 min(5,5,4,5,4) * (4-0+1) = 4 * 5 = 20 。

解题思路

例如 nums=[1,9,7,8,8,1], k=3。

其中面积最大的矩形,左边界下标 L=1,右边界下标 R=4。

我们尝试从 i=k,  j=k 出发,通过不断移动指针来找到最大矩形。比较 nums[i−1]和 nums[j+1]的大小,谁大就移动谁(一样大移动哪个都可以)。

定理:按照这种移动方式,一定会在某个时刻恰好满足 i=L且 j=R。

证明:如果 i先到达 L,那么此时 j<R。设 L 到 R之间的最小元素为 m,在方法一中我们知道 nums[L−1]<m,由于 nums[i−1]=nums[L−1]<m≤nums[j+1],那么后续一定是 j一直向右移动到 R。对于 j 先到达 R 的情况也同理。所以一定会在某个时刻恰好满足 i=L 且 j=R。

在移动过程中,不断用 nums[i] 和 nums[j] 更新矩形高度的最小值 minH,同时用 minH⋅(j−i+1)更新答案的最大值。

复杂度分析

时间复杂度:O(n),其中 n 为 nums的长度。
空间复杂度:O(1)。仅用到若干额外变量。

代码

class Solution {
public:int maximumScore(vector<int> &nums, int k) {int n = nums.size();int ans = nums[k], min_h = nums[k];int i = k, j = k;for (int t = 0; t < n - 1; t++) { // 循环 n-1 次if (j == n - 1 || i && nums[i - 1] > nums[j + 1]) {min_h = min(min_h, nums[--i]);} else {min_h = min(min_h, nums[++j]);}ans = max(ans, min_h * (j - i + 1));}return ans;}
};

这篇关于LeetCode每日一题[C++]-1793.好子数组的最大分数的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/825586

相关文章

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素(O(1)) 当我们要频繁的查找某个元素,第一哈希表O(1),第二,二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储,只要开26个c

【C++ Primer Plus习题】13.4

大家好,这里是国中之林! ❥前些天发现了一个巨牛的人工智能学习网站,通俗易懂,风趣幽默,忍不住分享一下给大家。点击跳转到网站。有兴趣的可以点点进去看看← 问题: 解答: main.cpp #include <iostream>#include "port.h"int main() {Port p1;Port p2("Abc", "Bcc", 30);std::cout <<

hdu2241(二分+合并数组)

题意:判断是否存在a+b+c = x,a,b,c分别属于集合A,B,C 如果用暴力会超时,所以这里用到了数组合并,将b,c数组合并成d,d数组存的是b,c数组元素的和,然后对d数组进行二分就可以了 代码如下(附注释): #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<que

C++包装器

包装器 在 C++ 中,“包装器”通常指的是一种设计模式或编程技巧,用于封装其他代码或对象,使其更易于使用、管理或扩展。包装器的概念在编程中非常普遍,可以用于函数、类、库等多个方面。下面是几个常见的 “包装器” 类型: 1. 函数包装器 函数包装器用于封装一个或多个函数,使其接口更统一或更便于调用。例如,std::function 是一个通用的函数包装器,它可以存储任意可调用对象(函数、函数

C++11第三弹:lambda表达式 | 新的类功能 | 模板的可变参数

🌈个人主页: 南桥几晴秋 🌈C++专栏: 南桥谈C++ 🌈C语言专栏: C语言学习系列 🌈Linux学习专栏: 南桥谈Linux 🌈数据结构学习专栏: 数据结构杂谈 🌈数据库学习专栏: 南桥谈MySQL 🌈Qt学习专栏: 南桥谈Qt 🌈菜鸡代码练习: 练习随想记录 🌈git学习: 南桥谈Git 🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈�

【C++】_list常用方法解析及模拟实现

相信自己的力量,只要对自己始终保持信心,尽自己最大努力去完成任何事,就算事情最终结果是失败了,努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一:什么是list? •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二:list常用接口 •🌰1.默认成员函数 🔥构造函数(⭐) 🔥析构函数 •🌰2.list对象

06 C++Lambda表达式

lambda表达式的定义 没有显式模版形参的lambda表达式 [捕获] 前属性 (形参列表) 说明符 异常 后属性 尾随类型 约束 {函数体} 有显式模版形参的lambda表达式 [捕获] <模版形参> 模版约束 前属性 (形参列表) 说明符 异常 后属性 尾随类型 约束 {函数体} 含义 捕获:包含零个或者多个捕获符的逗号分隔列表 模板形参:用于泛型lambda提供个模板形参的名

hdu 1166 敌兵布阵(树状数组 or 线段树)

题意是求一个线段的和,在线段上可以进行加减的修改。 树状数组的模板题。 代码: #include <stdio.h>#include <string.h>const int maxn = 50000 + 1;int c[maxn];int n;int lowbit(int x){return x & -x;}void add(int x, int num){while

6.1.数据结构-c/c++堆详解下篇(堆排序,TopK问题)

上篇:6.1.数据结构-c/c++模拟实现堆上篇(向下,上调整算法,建堆,增删数据)-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小): 2.2 C语言代码(手写堆) 2.3 C++代码(使用优先级队列 priority_queue)

poj 3723 kruscal,反边取最大生成树。

题意: 需要征募女兵N人,男兵M人。 每征募一个人需要花费10000美元,但是如果已经招募的人中有一些关系亲密的人,那么可以少花一些钱。 给出若干的男女之间的1~9999之间的亲密关系度,征募某个人的费用是10000 - (已经征募的人中和自己的亲密度的最大值)。 要求通过适当的招募顺序使得征募所有人的费用最小。 解析: 先设想无向图,在征募某个人a时,如果使用了a和b之间的关系