美文网首页
leetcode 300 最长上升子序列

leetcode 300 最长上升子序列

作者: 橘子煲汤 | 来源:发表于2019-02-21 13:06 被阅读0次

这个题目一开始没看清楚

输入: [10,9,2,5,3,7,101,18]

输出: 4

解释: 最长的上升子序列是 [2,3,7,101],它的长度是 4。

我理解成了最长上升连续子序列 这样的话答案应该是3而不是实例种的4 虽然写错了 但还是把我使用单调栈方式写的最长连续子序列的代码贴出来

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        stack<int> in;
        int ans=0,Ans=0;
        in.push(nums[0]);
        for(int i = 1;i<n;i++)
        {
            if(nums[i]<in.top())
            {
                ans=0;
                while(!in.empty())
                {
                    in.pop();
                    ans++;
                }
                Ans = max(ans,Ans);
               in.push(nums[i]);
            }
            else
            {
                in.push(nums[i]);
            }
            
        }
        //获取数量
      
        return Ans;
    }
};

相关文章

网友评论

      本文标题:leetcode 300 最长上升子序列

      本文链接:https://www.haomeiwen.com/subject/xssryqtx.html