首页 > (补充)区间最小数乘区间和的最大值,一道字节跳动高频面试题
头像
一个搬砖的胖子
编辑于 2021-02-25 16:02
+ 关注

(补充)区间最小数乘区间和的最大值,一道字节跳动高频面试题

前言

本文章是对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年头条的校招笔试题目。
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; 
}

更多模拟面试

全部评论

(1) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐