区间最小数乘区间和的最大值——头条(字节跳动)校招笔试高频题目

2021年3月5日15:22:08 发表评论 414 views
  • 挑选一个区间,区间值为区间和乘以区间内最小的数的值,求区间值最大的区间( 字节跳动-国际化-前端)[1]
  • 无序数组,求一个值最大的区间,区间计算方案为:区间和 * 区间最小值( 字节跳动-电商-后端)[2]
  • [3,1,6,4,5,2],对于任意子序列可以计算一个X值,X=sum(subArray) * min(subArray),求最大X( 字节跳动-商业化-前端)[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(!() && 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; 
}

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: