区间内最小的数字乘以区间总和的最大值 - 今日头条（字节跳动）入学笔试高频题

• 选择一个区间。间隔值是间隔之和乘以间隔中的最小数。找到间隔值最大的 Interval (ByteDance-Internationalization-Front-end) [1]
• 无序字符串，找到值最大的间隔。区间计算方案为：区间和*最小区间值（字节跳动电商-后端）[2]
• [3,1,6,4,5,2]，X的取值可以为对任意子序列计算，X=sum(substring) * min(substring)，求max X（字节跳动-商业化-前端）[3]

这其实是2018年头条笔试的一道题.?

矩阵中的所有元素都是非负数。

输入两行。第一行n表示数组的长度，第二行表示数组的序列。打印最大值。

输入
3
6 2 1
输出
36
解释：条件区间为 [6] = 6 * 6 = 36；

问题分析

方法一：暴力。问题是求max（区间和*区间的最小值），对应区间的最小值一定是数组的指定元素。因此，可以对数组进行编号。计数时，将每个元素（设置为x）作为区间的最小值。查找 x 左右第一个小于 x 的元素。将左边界和右边界的索引分别写为 l 和 r。查找限制时计算当前区间的总和。那么以x为区间最小值的最大计算区间一定是[l+1,r-1]区间和*x。整个算法的时间复杂度为O(N²)。

方法2：单调堆栈。第一种方法求每个元素左右边界的复杂度是O(N)。通过单调栈数据结构可以优化为O(1)，因此优化后算法的总时间复杂度可以达到O(N)。

对于还没有接触过单调集的同学，建议选LC84。直方图中最大的矩形。其实这道题是LC 84的改编版。

代码

//单调栈，时间复杂度O(N)
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
const int N = 500000+10;
int a[N];
int dp[N];
stack<int> s;
int main()
{
    int n,res=0;
    cin >> n;
    for(int i = 0; i < n; i ++) cin >> a[i];
    //前缀和便于快速求区间和，例如求[l,r]区间和=dp[r+1]-dp[l]。l和r的取值范围是[0,n)
    for(int i = 1; i <= n; i ++) dp[i] = dp[i-1] + a[i-1]; 
    for(int i = 0; i < n; i ++) {
        while(!() && a[i] <= a[()]) {
            int peak = a[()];
            ();
            int l = ()? -1 : ();
            int r = i; 
            //l和r是边界，因此区间是[l+1,r-1]，其区间和dp[r+1]-dp[l]
            int dist = dp[r] - dp[l+1];
            res = max(res,peak*dist);
        }
        (i);
    }
    while(!())
    {
        int peak = a[()];
        ();
        int l = ()? -1 : ();
        int r = n; 

        int dist = dp[r] - dp[l+1];
        res = max(res,peak*dist);
    }
    cout << res << endl; 
}