解题思路

给定长度为 n 的正整数数组 nums，表示各连续频段的质量评分。 对任意一个连续非空子数组（组合），其「组合质量系数」定义为： 该组合内的最小质量评分 × 组合长度。 目标是求所有组合中该值的最大值。

这是经典问题：对每个元素把它当作组合中的最小值，尽量向左、向右扩展，直到遇到更小的元素为止。 这样该元素可主导的最大组合长度 = right[i] - left[i] - 1，其中：

• left[i]：i 左侧最近的 严格小于 nums[i] 的位置（没有则为 -1）
• right[i]：i 右侧最近的 小于等于 nums[i] 的位置（没有则为 n）

上述边界可用**单调栈（递增栈）**在 O(n) 时间内求出：

• 从左到右维护“严格递增”栈，得到 left[i]
• 从右到左维护“非严格递增”（> 弹栈）得到 right[i]

随后枚举每个 i，计算面积（质量系数）： area = nums[i] * (right[i] - left[i] - 1)，取最大即可。 这与“柱状图中最大的矩形面积”是同一思路。

复杂度分析

• 时间复杂度：O(n)，每个元素最多进栈出栈一次。
• 空间复杂度：O(n)，需要 left、right 数组与单调栈。

代码实现

Python

# 题面功能放在外部函数，主函数只负责输入输出

from typing import List

def max_quality(nums: List[int]) -> int:
    n = len(nums)
    left = [-1] * n   # 左边最近的严格更小元素位置
    right = [n] * n   # 右边最近的小于等于元素位置

    # 单调递增栈（存下标），用于求 left（严格小于）
    stack = []
    for i in range(n):
        # 保证栈顶元素对应值 < nums[i]
        while stack and nums[stack[-1]] >= nums[i]:
            stack.pop()
        left[i] = stack[-1] if stack else -1
        stack.append(i)

    # 清空栈，反向求 right（小于等于）
    stack.clear()
    for i in range(n - 1, -1, -1):
        # 使得下一个不满足 > 的位置为 right（即 <=）
        while stack and nums[stack[-1]] > nums[i]:
            stack.pop()
        right[i] = stack[-1] if stack else n
        stack.append(i)

    ans = 0
    for i in range(n):
        width = right[i] - left[i] - 1
        area = nums[i] * width
        if area > ans:
            ans = area
    return ans

if __name__ == "__main__":
    # ACM 风格输入：第一行 n，接着 n 行为各评分
    import sys
    data = sys.stdin.read().strip().split()
    n = int(data[0])
    nums = list(map(int, data[1:1+n]))
    print(max_quality(nums))

Java

// 类名必须为 Main，ACM 风格从标准输入读取
import java.util.*;

public class Main {

    // 外部函数：计算最大组合质量系数
    public static int maxQuality(int[] nums) {
        int n = nums.length;
        int[] left = new int[n];   // 左侧最近严格更小的位置
        int[] right = new int[n];  // 右侧最近小于等于的位置
        Arrays.fill(left, -1);
        Arrays.fill(right, n);

        // 单调递增栈（存下标），用于求 left（严格小于）
        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            // 保证栈内对应值严格递增
            while (!stack.isEmpty() && nums[stack.peek()] >= nums[i]) {
                stack.pop();
            }
            left[i] = stack.isEmpty() ? -1 : stack.peek();
            stack.push(i);
        }

        // 清栈，反向求 right（小于等于）
        stack.clear();
        for (int i = n - 1; i >= 0; i--) {
            // 弹出所有 > nums[i] 的元素，保留 <= 的第一个作为边界
            while (!stack.isEmpty() && nums[stack.peek()] > nums[i]) {
                stack.pop();
            }
            right[i] = stack.isEmpty() ? n : stack.peek();
            stack.push(i);
        }

        int ans = 0;
        for (int i = 0; i < n; i++) {
            int width = right[i] - left[i] - 1;
            int area = nums[i] * width; // 质量系数
            if (area > ans) ans = area;
        }
        return ans;
        }

    public static void main(String[] args) {
        // 数据范围不大，直接使用 Scanner
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) nums[i] = sc.nextInt();
        System.out.println(maxQuality(nums));
    }
}

C++

// ACM 风格：标准输入输出，函数外实现核心逻辑
#include <bits/stdc++.h>
using namespace std;

// 计算最大组合质量系数
int max_quality(const vector<int>& nums) {
    int n = (int)nums.size();
    vector<int> left(n, -1);  // 左侧最近严格更小
    vector<int> right(n, n);  // 右侧最近小于等于
    vector<int> st;

    // 求 left：维护单调递增栈（值严格递增）
    for (int i = 0; i < n; ++i) {
        while (!st.empty() && nums[st.back()] >= nums[i]) st.pop_back();
        left[i] = st.empty() ? -1 : st.back();
        st.push_back(i);
    }

    // 清空栈，反向求 right：找到第一个 <= 的位置
    st.clear();
    for (int i = n - 1; i >= 0; --i) {
        while (!st.empty() && nums[st.back()] > nums[i]) st.pop_back();
        right[i] = st.empty() ? n : st.back();
        st.push_back(i);
    }

    long long ans = 0;
    for (int i = 0; i < n; ++i) {
        long long width = right[i] - left[i] - 1;
        long long area = 1LL * nums[i] * width; // 质量系数
        if (area > ans) ans = area;
    }
    return (int)ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    if (!(cin >> n)) return 0;
    vector<int> nums(n);
    for (int i = 0; i < n; ++i) cin >> nums[i];
    cout << max_quality(nums) << "\n";
    return 0;
}

题目内容

在 $5G$ 网络规划中，运营商需要评估不同频段组合的资源利用率。每个频段有一个特定的带宽质量评分(数值越大表示质量越好)。当多个连续频段被组合使用时，它们的整体利用率由「组合质量系数」决定，该系数等于组合中最差频段的质量评分乘以组合的频段数量。

作为网络优化工程师，你需要计算所有可能的连续频段组合的利用率，找出其中最大的「组合质量系数」，从而确定最优的频段分配方案。

问题定义

给定一个整数数组 $nums$ ，表示一系列连续频段的质量评分。计算所有可能的连续非空频段组合的「组合质量系数」，并返回其中的最大值。

连续非空频段组合：指一组连续的频段，例如频段质量序列 $[1,2,3]$ 的组合包括：

$[1]、[2]、[3]$

$[1,2]、[2,3]$

$[1,2,3]$

组合质量系数：该组合中最低质量评分乘以频段数量。

输入描述

第 $1$ 行：整数 $n$ ，表示频段数量 $(1≤n≤10000)$ 。

第 $2$ ~ $n+1$ 行：$n$ 个整数，表示每个频段的质量评分 $(1≤nums[i]≤10000)$ 。

输出描述

一个整数，表示所有组合中最大的「组合质量系数」。

样例1

输入

2
1
2

输出

2

说明

组合 $[1] →$ 系数 $=1×1=1$

组合 $[2]→$ 系数 $=2×1=2$

组合 $[1,2]→$ 最低质量 $=1$ ，频段数 $=2→$ 系数 $=1×2=2$

最大系数为 $2$ ，来自 $[2]$ 或 $[1,2]$ 。

样例2

输入

3
5
3
4

输出

9

说明

组合 $[5]→$ 最低质量 $=5$ ，频段数 $=1→$ 系数 $=5×1=5$

组合 $[5,3]→$ 最低质量 $=3$ ，频段数 $=2→$ 系数 $=3×2=6$

组合 $[5,3,4]→$ 最低质量 $=3$ ，频段数 $=3→$ 系数 $=3×3=9$

组合 $[3]→$ 最低质量 $=3$ ，频段数 $=1→$ 系数 $=3×1=3$

组合 $[3,4]→$ 最低质量 $=3$ ，频段数 $=2→$ 系数 $=3×2=6$

组合 $[4]→$ 最低质量 $=4$ ，频段数 $=1→$ 系数 $=4×1=4$

最大系数为 $9$ ，来自组合 $[5,3,4]$ 。