这道题的正解是 单调栈(柱状图最大矩形),但是我们用朴素解法 向左右扩展 也能在考试时拿到一定的分数。
题意:对数组 nums 的任意连续子数组,其「组合质量系数」为「子数组最小值 × 长度」。求所有连续子数组中该值的最大值。
朴素做法:把每个下标 i 当作子数组里的最小值,尽量向左、向右扩展,直到遇到比 nums[i] 更小的元素为止。此时以 nums[i] 为最小值的最长区间长度为 R−L+1,系数为 nums[i]×(R−L+1),对所有 i 取最大。
n 较小时 O(n2) 可通过;当 n 接近 105 时会超时,需要后面的单调栈做法。
在 5G 网络规划中,运营商需要评估不同频段组合的资源利用率。每个频段有一个特定的带宽质量评分(数值越大表示质量越好)。当多个连续频段被组合使用时,它们的整体利用率由「组合质量系数」决定,该系数等于组合中最差频段的质量评分乘以组合的频段数量。
作为网络优化工程师,你需要计算所有可能的连续频段组合的利用率,找出其中最大的「组合质量系数」,从而确定最优的频段分配方案。
问题定义
给定一个整数数组 nums ,表示一系列连续频段的质量评分。计算所有可能的连续非空频段组合的「组合质量系数」,并返回其中的最大值。
Scan the QR code below with WeChat to sign in
First-time scan will create your account automatically
请使用微信扫描下方二维码完成注册