lintcode 子数组问题（最全的面试子数组问题）

前言

2017年的六月份到九月份，陆陆续续在leetcode上面刷了130道题目。

眼瞅着明年开年就要开始求职找实习。于是重新开始了一波刷题。

现在的选择是使用lintcode，相比leetcode，我认为lintcode更好的是：

1.有中文版的，用起来比较熟悉。

2.记笔记比较方便。

3.题目比leetcode少一些，题不在多，在于精。

4.可以创建群组，一起刷题，看到群里刷题动态（包括代码和笔记）。

5.有倒计时功能。（一般简单15min，中等30min，困难45min），这个比较能模拟真实面试场景。

正题

这次参与刷题的一共有四人（嘟嘟、琼琼、东东、博主）。

41.最大子数组

dp[i] = max(dp[i-1],0)+a[i] （空间可用O(1)）

PS：百度面试题

42.最大子数组2

找两个不重叠的子数组，让和最大。

双向DP。（前向后向分别找最大）

43.最大子数组3

给一个k，找出k个不重叠的子数组，让和最大。

local[i][m]表示到第i个位置，分为m个子数组的局部最大和（最后一个子数组包含第i个元素）

global[i][m]表示到第i个位置，分为m个子数组的全局最大和（最后一个子数组不一定包含第i个元素）

要这样去分，是因为状态转移的时候需要用到。比如第i+1个位置的元素能不能拼到最后一个子数组里，还是另开一个子数组。

状态转移方程为：

local[i][m] = max(global[i-1][m-1],local[i-1][m])+nums[i] （需要包含第i个元素，max里面第一项表示新开一个子数组，第二项表示把第i个元素拼到最后一个子数组上）

global[i][m] = max(local[i][m],global[i-1][m])（从当前局部最大和之前的全局最大中找）

AC代码：

class Solution {
public:
    /*
     * @param nums: A list of integers
     * @param k: An integer denote to find k non-overlapping subarrays
     * @return: An integer denote the sum of max k non-overlapping subarrays
     */
    int maxSubArray(vector<int> &nums, int k) {
        // write your code here
        //到第i个位置在内，分为m个不重叠的子数组
        //要看包含第i-1个位置(分为m个)，到第i-1个位置、不一定包含第i-1个位置(分为m-1个)
        
        int len = nums.size();
        vector<vector<int> > local(len,vector<int>(k)); //一定包含第i位置
        vector<vector<int> > global(len,vector<int>(k)); //不一定包含第i个位置
        
        for(int i=0;i<len;++i){
            for(int m=0;m<k;++m){
                if(m>i) break;
                if(m==0){
                    local[i][m] = i==0?nums[i]:max(local[i-1][m],0)+nums[i];
                    global[i][m] = i==0?nums[i]:max(local[i][m],global[i-1][m]);
                }
                else{
                    local[i][m] = i-1>=m?max(global[i-1][m-1],local[i-1][m])+nums[i]:global[i-1][m-1]+nums[i];
                    global[i][m] = i-1>=m?max(local[i][m],global[i-1][m]):local[i][m];
                }
            }
        }
        return global[len-1][k-1];
    }
};

44.最小子数组
和41最大子数组类似

45.最大子数组差

和42最大子数组2类似。

双向DP。（前向最大 后向最小）和（前向最小 后向最大）

138.子数组之和

找到和为0的子数组，返回起始位置和结束位置。

用sum[i]记录到0位置到i位置的和，O(n^2)方法会超时。【python的O(n^2)可以过，面试估计就GG了。。】

类似2 sum的题目，使用map，把之前的和都存到map中。

存在的话，说明已经找到了。

初始化map[0]=-1；

AC代码：

class Solution {
public:
    /*
     * @param nums: A list of integers
     * @return: A list of integers includes the index of the first number and the index of the last number
     */
    vector<int> subarraySum(vector<int> &nums) {
        // write your code here
        int len=nums.size(), sum=0;
        vector<int> res(2);
        map<int,int> mp;
        mp[0]=-1;
        
        for(int i=0;i<len;++i){
            sum+=nums[i];
            if(mp.find(sum)!=mp.end()){
                res[0]=mp[sum]+1,res[1]=i;
                return res;
            }
            mp[sum]=i;
        }
    }
};

139.最接近零的子数组和

sum[i]表示0到i位置的和，那么求sum[j]-sum[i]就可以求得子数组和，然后再选择最小的。这样时间是O（n^2），我们只需要找最接近0的，那么我们何不将这些sum数组排序，然后挨着的两个找呢。

191.乘积最大子序列

比较笨拙的办法是我之前使用的：

由于要求最大乘积，而且都是整数。那么我们只用考虑负数的个数即可，如果是偶数，全部连乘即可。如果是奇数个，那么只用考虑最左边的负数（左右两边分别单独连乘）和最右边的负数（左右两边分别单独连乘）。然后需要用0来做边界。

后来和同学讨论，发现这题其实很简单。。。

由于是连乘最大。我们只用保留之前的最大和最小即可。（最小的乘以负数变为最大）

两种方法都可以过，但是第二种写起来会简单许多：乘积最大子序列

402.连续子数组求和

类似41，只是需要返回边界。可以使用双指针，或者先得到右边界再算左边界

617.最大平均子数组（好题！！）

长度大于等于K的子数组平均值最大。

拿到这题首先是没有思路，想到的方法只能是O（n^2），但是提示我会超时，n的个数达到10^4。

我们的目标是求这个平均值，那这个值的范围在哪里呢？

令数组中最小元素为min，最大值为max。那么平均值的范围必须是[min,max]。

我们设平均值为x，如果有一个O（n）的方法能判断长度大于等于K的子数组平均值大于x或者小于等于x，这样时间复杂度就变成了O（n*log2(max-min)）。因为我们将left=min，right=max，mid=(left+right)/2，如果最大平均值大于mid，直接让left=mid；如果最大平均值小于等于mid，让right=mid。

我们使用sum[i]表示0位置到i位置的元素之和。由于之前是平均值不确定，数组的长度不确定，i到j的平均值为(sum[j]-sum[i])/(j-i)。这样的计算必须是O（n^2）。

而现在我们只需要判断最大平均值是不是大于mid。我们将每个元素都减去mid，我们现在只需要判断最大平均值是不是大于0。而(sum[j]-sum[i])/(j-i)是不是大于0，直接等价为sum[j]-sum[i]是不是大于0。

而算sum[j]-sum[i]里的最大值不需要枚举每个i和j。我们在遍历数组的时候只需要记录和位置j 距离为k以上的最小值即可。而这个最小值是可以很轻易的得到的。

AC代码：

class Solution {
public:
    /*
     * @param nums: an array with positive and negative numbers
     * @param k: an integer
     * @return: the maximum average
     */
    double maxAverage(vector<int> &nums, int k) {
        int len = nums.size();
        double l=nums[0],r=nums[0],mid,eps=1e-6;
        vector<double> sum(len+1);
        for(int i=1;i<len;++i){
            l = min(l,double(nums[i]));
            r = max(r,double(nums[i]));
        }
        
        while(r-l>eps){
            mid = (r+l)/2;
            double pre=0;
            bool flag=false;
            
            sum[0]=0;
            for(int i=1;i<=len;++i)
                sum[i]=sum[i-1]+nums[i-1]-mid;
            
            for(int i=k;i<=len;++i){
                if(sum[i]-pre>eps){
                    flag=true;
                    break;
                }
                pre = min(pre,sum[i-k+1]);
            }
            if(flag) l=mid;
            else r=mid;
        }
        return r;
    }
};

番外

想到了最近今日头条实习生面试的一道题目。

题意是让求一个子数组，让子数组里的最小元素乘以子数组的和最大。（最小数字*区间和 最大）

这个题目的来源是POJ 2796

当然O（n^2）的方法面试官当然是不满意的。

现在最主要的问题是确定每个数字的边界，在左边找一个比它小的第一个元素位置，在右边找一个比它小的第一个元素的边界。然后计算每个数字乘以对应的区间和即可。

如何找每个数字的边界，一般的做法是维护一个单调递增栈。遍历数组，如果比栈顶大，就入栈，如果比栈顶小，说明边界找到了。(如果比栈顶小，那么栈顶元素的左边界是次顶元素的位置，右边界是当前元素的位置)

AC代码：(nums[i]用cin的话会超时，scanf有输入优化)

#include<iostream>
#include<stack>
#include<cstdio>
#define maxn 100005
using namespace  std;

long long nums[maxn];
long long sum[maxn]; //记录和

int main(){
    int n,i;
    int l,r; //结果的左边界，右边界。
    long long ans,tmp; //最后的结果

    while(cin>>n){
        ans = l = r =  0;
        stack<int> stac; //单调递增栈
        for(i=0;i<n;++i){
            scanf("%lld",&nums[i]);
            sum[i]=i==0?nums[i]:sum[i-1]+nums[i];
        }
        nums[n]=0;

        for(i=0;i<=n;++i){
            while(!stac.empty()&&nums[stac.top()]>nums[i]){
                long long cur = nums[stac.top()];
                stac.pop();
                if(stac.empty()) tmp = sum[i-1]*cur;
                else tmp = (sum[i-1]-sum[stac.top()])*cur;
                if(tmp>ans) ans=tmp,r=i-1,l=stac.empty()?0:stac.top()+1;
            }
            stac.push(i);
        }
        cout<<ans<<endl;
        cout<<l+1<<" "<<r+1<<endl;
    }
    return 0;
}

同样的类型还有leetcode 84

给一个数组，让求数组构成的图里面的最大矩形。

问题来了，在左边找一个比它小的第一个元素位置，在右边找一个比它小的第一个元素的边界。然后计算每个数字乘以对应的区间长度即可。

是不是和上面的题目特别相似啊。。。

AC代码：

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int len = heights.size(),res=0;
        heights.push_back(0);
        
        stack<int> stac;
        for(int i=0;i<=len;++i){
            while(!stac.empty()&&heights[stac.top()]>heights[i]){
                int tmp = heights[stac.top()];
                stac.pop();
                tmp = stac.empty()?tmp*i:tmp*(i-1-stac.top());
                res = max(res,tmp);
            }
            stac.push(i);
        }
        return res;
    }
};