题目描述

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

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

方法一 动态规划

解题思路

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


状态转移方程的含义为考虑所有小于的，并且，的大小就是最大的的大小加1。
初识时，状态数组应全部赋值为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;
    }
};

复杂度分析

  • 时间复杂度：更新和时，两层循环需要的时间复杂度为
  • 空间复杂度：使用两个长度为的数组，空间复杂度为

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

解题思路

方法一的动态规划方法时间复杂度较高，因为每次更新数组时都需要再遍历一遍。可以考虑结合二分查找来实现求最长递增子序列的另一种动态规划的方法。定义数组，表示长度为的最长递增子序列的末尾元素的最小值，用变量来记录目前最长递增子序列的长度。开始时，为1，。依次遍历数组中的每个元素，并更新数组和的值，如果，说明目前遍历到的这个数大于目前最长递增子序列末尾元素的最小值，递增子序列长度应该加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;
    }
};

复杂度分析

  • 时间复杂度：遍历数组时，通过二分查找在数组中找到的合适位置，每次二分查找时间复杂度为，所以总的时间复杂度为
  • 空间复杂度：使用三个长度为的数组，空间复杂度为