（补充）区间最小数乘区间和的最大值，一道字节跳动高频面试题

前言

本文章是对CodeTop 的补充，汇总那些在Leetcode上找不到的面试高频题

来看一下几篇面经的原文叙述

• 挑选一个区间，区间值为区间和乘以区间内最小的数的值，求区间值最大的区间（2021.1 字节跳动-国际化-前端）^[1]
  
• 无序数组，求一个值最大的区间，区间计算方案为：区间和 * 区间最小值（2020.09 字节跳动-电商-后端）^[2]
  
• [3,1,6,4,5,2]，对于任意子序列可以计算一个X值，X=sum(subArray) * min(subArray)，求最大X（2020.07 字节跳动-商业化-前端）^[3]

这其实是18年头条的校招笔试题目。

题目描述

给定一个数组，要求选出一个区间, 使得该区间是所有区间中经过如下计算的值最大的一个：区间中的最小数 * 区间所有数的和。

数组中的元素都是非负数。

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

输入
3
6 2 1
输出
36
解释：满足条件区间是[6] = 6 * 6 = 36;

题目分析

方法一：暴力。题目是找max(区间和 * 区间最小值)，而满足的区间最小值一定是数组的某个元素。因此可以枚举数组，枚举时每个元素（设为x）作为区间最小值，在x左右两侧找到第一个比x小的元素，分别记录左右边界的下标为l,r，寻找边界时计算当前区间的和。那么以x为区间最小值的最大计算区间一定是[l+1,r-1]区间和*x。整个算法的时间复杂度是O(N²)。

方法二：单调栈。方法一中找每个元素左右边界的复杂度是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(!s.empty() && a[i] <= a[s.top()]) {
            int peak = a[s.top()];
            s.pop();
            int l = s.empty()? -1 : s.top();
            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);
        }
        s.push(i);
    }
    while(!s.empty())
    {
        int peak = a[s.top()];
        s.pop();
        int l = s.empty()? -1 : s.top();
        int r = n; 

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