题解 | #牛妹的面试#

牛妹的面试

http://www.nowcoder.com/practice/2818df3e10c44f859e49048875a71d34

题目描述

众所周知，牛妹是一个offer收割姬，这次面试她遇到了这样的一个问题。

给了一个序列，让找出最长的“凸子序列”
“凸子序列”：数列中有一个 $x_i$ ,使得所有 $x_0<x_1<x_2….x_{i-1}<x_i$ 且 $x_i>x_{i+1}>….>x_n$
eg：12345431,是山峰序列，12345234不是山峰序列
注：单调递增或单调递减序列也算山峰序列；单独一个数是长度为1的山峰序列
明确条件：1.子序列与子串不同，子序列不要求连续而子串要求连续。2.要求严格上升。

方法一动态规划

解题思路

此题容易联想到比较经典的求最长递增子序列问题，这是使用动态规划的经典问题。先考虑最长递增子序列问题，定义 $dp[i]$ 为考虑前 $i$ 个数字，以第 $i$ 个数字结尾的最长递增子序列的长度，这里注意第 $i$ 个数字必须被选择。状态转移方程为：

$dp[i]=max(dp[j])+1,0\le j<i,num[j]<num[i]$
状态转移方程的含义为考虑所有小于 $num[i]$ 的 $num[j]$ ，并且 $j<i$ ， $dp[i]$ 的大小就是最大的 $dp[j]$ 的大小加1。
初识时，状态数组应全部赋值为1。
那么，整个数组的最长递增子序列的长度为 $max(dp[i]),0\le i <n$ 。
类似地，这道题需要找“山峰序列”，我们可以分别正向和反向找两遍最长递增子序列，分别用 $up[i]$ 和 $down[i]$ 来表示不同的状态，根据上文的定义，可以看出 $up[i]$ 是必须选择第 $i$ 个数组，以第 $i$ 个数字结尾的最长递增子序列的长度，所以反向更新时， $down[i]$ 是必须选择第 $i$ 个数组，以第 $i$ 个数字开始的最长递减子序列的长度。 $max(up[i]+down[i])-1,0\le i<n$ 即为最长山峰序列的长度。

图片说明

可以看出， $up[i]$ 和 $down[i]$ 中分别存储的是以 $nums[i]$ 结尾、开头的最长递增、递减子序列的长度，所以 $up[i]+down[i]-1$ 的最大值即为最长山峰序列的长度。

代码示例

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 返回最大山峰序列长度
     * @param numberList int整型vector 给定的序列
     * @return int整型
     */
    int mountainSequence(vector<int>& numberList) {
        int ret = 0, n = numberList.size();
        // 状态数组
        // up[i]: 以num[i]结尾的最长递增子序列的长度
        // down[i]: 以num[i]开头的最长递减子序列的长度
        vector<int> up(n ,1), down(n, 1);
        // 根据状态转移方程更新up
        for(int i=1;i<n;i++)
            for(int j=0;j<i;j++)
                if(numberList[j]<numberList[i])
                    up[i] = max(up[i], up[j]+1);
        // 类似地，反向更新down
        for(int i=n-2;i>=0;i--)
            for(int j=n-1;j>i;j--)
                if(numberList[j]<numberList[i])
                    down[i] = max(down[i], down[j]+1);
        // 求出up[i]+down[i]-1的最大值即为最长山峰序列的长度
        for(int i=0;i<n;i++)
            ret = max(ret, up[i]+down[i]-1);
        return ret;
    }
};

复杂度分析

时间复杂度：更新 $up$ 和 $down$ 时，两层循环需要的时间复杂度为 $O(n^2)$
空间复杂度：使用两个长度为 $n$ 的 $dp$ 数组，空间复杂度为 $O(n)$

方法二动态规划+二分查找

解题思路

方法一的动态规划方法时间复杂度较高，因为每次更新 $dp$ 数组时都需要再遍历一遍。可以考虑结合二分查找来实现求最长递增子序列的另一种动态规划的方法。定义数组 $d[i]$ ，表示长度为 $i$ 的最长递增子序列的末尾元素的最小值，用变量 $len$ 来记录目前最长递增子序列的长度。开始时， $len$ 为1， $d[1]=nums[0]$ 。依次遍历数组中的每个元素，并更新数组 $dp$ 和 $len$ 的值，如果 $nums[i]>d[len]$ ，说明目前遍历到的这个数大于目前最长递增子序列末尾元素的最小值，递增子序列长度应该加1， $len=len+1$ ；否则，在 $d[1...len]$ 中找到满足 $d[i-1]<nums[j]<d[i]$ 的下标 $i$ 并更新 $d[i]=nums[j]$ 以满足前面叙述的 $d[i]$ 的定义。由于数组 $d$ 是单调递增的，所以可以使用二分查找的方法寻找下标 $i$ ，从而优化时间复杂度。步骤如下图所示

图片说明

由这个方法启发，我们可以优化方法一的时间复杂度。在 $up$ 和 $down$ 数组之外建立一个辅助数组 $d$ ， $d[i]$ 中存储长度为 $i$ 的最长递增子序列结尾元素的最小值， $up[i]$ 和 $down[i]$ 的值用前文提到的 $d$ 数组长度 $len$ 更新。最后， $up[i]+down[i]-1$ 的最大值即为最长山峰序列的长度。

代码示例

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 返回最大山峰序列长度
     * @param numberList int整型vector 给定的序列
     * @return int整型
     */
    int mountainSequence(vector<int>& numberList) {
        int ret = 0, n = numberList.size();
        // up[i]: 以num[i]结尾的最长递增子序列的长度
        // down[i]: 以num[i]开头的最长递减子序列的长度
        // d[i]: 长度为i的最长递增子序列末尾元素的最小值
        vector<int> up(n ,1), down(n, 1), d(1, 0);
        // 遍历数组，先更新d，然后根据d的长度更新up
        for(int i=0;i<n;i++) {
            // 如果遍历到的第i个数比d的最后一个数大，最长递增子序列长度需增加
            if(numberList[i] > d.back()) {
                d.push_back(numberList[i]);
            }
            // 否则，二分查找到第i个数应该替换的位置
            else {
                auto iter = lower_bound(d.begin(), d.end(), numberList[i]); //O(logn)
                *iter = numberList[i];
            }
            // 根据d的长度更新up
            up[i] = d.size() - 1;
        }

        // 重置数组d以完成down的更新
        d.resize(1);
        d[0] = 0;
        // 类似地，反向更新down
        // 反向遍历数组，先更新d，然后根据d的长度更新down
        for(int i=n-1;i>=0;i--) {
            // 如果遍历到的第i个数比d的最后一个数大，最长递增子序列长度需增加
            if(numberList[i] > d.back()){
                d.push_back(numberList[i]);
            }
            // 否则，二分查找到第i个数应该替换的位置
            else {
                auto iter = lower_bound(d.begin(), d.end(), numberList[i]);
                *iter = numberList[i];
            }          
            // 根据d的长度更新down
            down[i] = d.size() - 1;

        }

        // 求出up[i]+down[i]-1的最大值即为最长山峰序列的长度
        for(int i=0;i<n;i++)
            ret = max(ret, up[i]+down[i]-1);
        return ret;
    }
};