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

单调栈,LeetCode 1793. 好子数组的最大分数

一、题目

1、题目描述

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

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

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

2、接口描述

class Solution {
public:
    int maximumScore(vector<int>& nums, int k) {

    }
};

3、原题链接

1793. 好子数组的最大分数


二、解题报告

1、思路分析

贪心+双指针

和84. 柱状图中最大的矩形类似, 本质都是求最大矩形面积,只不过本题要求矩形包含k

那么我们考虑从k开始,双指针向两边遍历

双指针l,r初始指向k,如果nums[l - 1]大于nums[r + 1],就l--,否则r++

然后维护区间[l, r]内的最小值mi,矩形面积就是mi * (r - l + 1)

下面证明贪心策略的正确性:

假设最终答案矩形边界为L,R

那么一定有nums[L - 1] < nums[L],nums[R + 1] < nums[R],否则矩形可以进一步扩大

我们只需证明l ,r最终一定停留在L,R的位置

不失一般性的假设l先抵达L,此时由于nums[L - 1] < mi <= nums[r],故r会一直右移直到R

反之如果r先抵达R,亦然

2、复杂度

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

3、代码详解

class Solution {
public:
    int maximumScore(vector<int>& nums, int k) {
        int n = nums.size(), l = k, r = k, ret = nums[k];
        for(int i = 0, mi = nums[k]; i < n - 1; i++){
            if(r == n - 1 || (l && nums[l - 1] > nums[r + 1]))
                mi = min(mi, nums[--l]);
            else
                mi = min(mi, nums[++r]);
            ret = max(ret, (r - l + 1) * mi);
        }
        return ret;
    }
};


http://www.kler.cn/a/274301.html

相关文章:

  • 【学习记录】浏览器指纹相关学习记录(指纹介绍、获取指纹、修改指纹、随机指纹保护隐私等)
  • VLM--CLIP作分类任务的损失函数
  • Qt之QML应用程序开发:给应用程序添加图标文件
  • 高效处理PDF文件的终极工具:构建一个多功能PDF转换器
  • 【LeetCode】394、字符串解码
  • 投标心态:如何在“标海战术”中保持清醒的头脑?
  • 2、鸿蒙学习-申请调试证书和调试Profile文件
  • 0基础学习VR全景平台篇第145篇:图层控件功能
  • 综合练习(python)
  • GAMES101 学习3
  • 【计算机考研】408全年复习保姆级规划+资料
  • .Net Core 中间件验签
  • 华为组网:核心交换机旁挂防火墙,基于ACL重定向配置实验
  • Maven项目如何导入依赖包
  • Nginx安装教程
  • Springboot+Redis:实现缓存 减少对数据库的压力
  • fastjson反序列化攻略
  • 解决重装系统之后,开始菜单找不到Anaconda3相关图标
  • 快速从0-1完成聊天室开发——环信ChatroomUIKit功能详解
  • Java-SpringAop 编程式事物实现
  • 如何在三个简单步骤中为对象检测标注图像
  • C语言---指针的两个运算符:点和箭头
  • Java 多线程(抢CPU)
  • 面试算法-51-翻转二叉树
  • 【C语言进阶篇】自定义类型:结构体(上)
  • 堆排序(数据结构)