讨论/题目交流/有道算法题,一直没思路/
有道算法题,一直没思路

k>=3的任何正整数序列b1,b2,……,bk,如果这个序列满足其中的值先是增加,直到bj(1<j<k),后再减少,则这个序列称为气泡序列(b1 < b2 < · · · < bj 然后 bj > bj+1 > · · · > bk)。我们要在一个有n个正整数的序列a1,a2,……,an中找到最大好序列。
例如:序列a为 2 1 4 7 5 4 6 3 1,则最大好序列为2 4 7 5 4 3 1或是1 4 7 5 4 3 1,元素为7个。
如何设计算法,求出给定序列a中最大好序列的元素个数

展开讨论
Tommylee发起于 2020-04-01

题目

长度为 k 的正整数数组 b ,其中 k >= 3 。
如果能找到一个先递增再递减的子序列,称为气泡序列。
即子序列组成的新数组 c ,长度为 len,以第 j 个元素分割,从 c[0] 到 c[j] 是递增的,从 c[j] 到 c[len - 1] 是递减的。
求最大的气泡序列长度。

用例

输入:nums = [2,1,4,7,5,4,6,3,1]
输出:7

输入:nums = [1,2,3,4,5,4,3,2,1]
输出:9

输入:nums = [1,1,2,2,3,2,2,1,1]
输出:5

输入:nums = [3,2,1,2,3]
输出:0

输入:nums = [5,4,3,2,1]
输出:0

输入:nums = [1,2,3,4,5]
输出:0

思路

  1. 正反两次单调栈,将对应位置的栈中元素的数量保存起来
  2. 遍历每个位置,相加结果 -1 即为子序列长度
  3. 注意如果只有递增或递减不符合题目要求

答题

void f(vector<int>& nums, stack<int>& st, vector<int>& cnt, int i)
{
    if (!st.empty() && st.top() >= nums[i])
    {
        st.pop();
    }
    st.push(nums[i]);
    cnt[i] += st.size();
}

int lengthOfLongBallonSubsequence(vector<int>& nums)
{
    stack<int> st_inc;
    stack<int> st_dec;
    vector<int> inc(nums.size(), 0);
    vector<int> dec(nums.size(), 0);

    for (int i = 0; i < nums.size(); i++)
    {
        f(nums, st_inc, inc, i);
        f(nums, st_dec, dec, nums.size() - i - 1);
    }

    int ans = 0;
    for (int i = 0; i < nums.size(); i++)
    {
        ans = (inc[i] != 1 && dec[i] != 1) ? max(ans, inc[i] + dec[i] - 1) : ans;
    }
    return ans;
}

致谢

感谢您的观看,希望对您有帮助,欢迎热烈的交流!

如果感觉还不错就点个赞吧~

这是 我的leetcode ,帮助我收集整理题目,可以方便的 visual studio 调试,欢迎关注,star

2
展开全部 2 讨论