首页 > 试题广场 >

叠罗汉I

[编程题]叠罗汉I

热度指数：6546 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

给定一个int数组men，代表参加一场游戏依次来的每个人的身高，同时给定总人数n，要求一个人站在另一个人肩膀上，且下面的人比上面的人要更高一点。请返回最多能够叠的人数。注意参加游戏的人的先后顺序与原序列中的顺序应该一致保证，且n小于等于500。

测试样例：

[1,6,2,5,3,4],6

返回：4

算法知识视频讲解

Python

华科平凡

python解法，时间复杂度为nLogN，不能更简单了。

# -*- coding:utf-8 -*-
import bisect


class Stack:
    def getHeight(self, men, n):
        # write code here
        q = []
        for v in men:
            pos = bisect.bisect_left(q, v)
            if pos == len(q):
                q.append(v)
            else:
                q[pos] = v
        return len(q)

发表于 2017-10-07 14:29:01 回复(0)

maoger

恕我直言，“叠罗汉是一个著名的游戏”，不知道是否真的有人会这样玩。

发表于 2017-07-23 14:56:26 回复(0)

Python

Yannyezixin

这题有好多解法

思路一：

经典解法，求最长公共子序列问题，过程就不赘述了，解法可以上网搜搜 O(n ^ 2)

    # 最长公共子序列问题, 动态规划O(n^2)
    def getHeight1(self, men, n):
        if n < 1:
            return 0
        x = men
        y = sorted(men)
        dp = [[0] * (n + 1) for i in range(n + 1)]
        
        for i in range(1, n + 1):
            for j in range(1, n + 1):
                if x[i-1] == y[j-1]:
                    dp[i][j] = dp[i - 1][j - 1] + 1
                else:
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
        return dp[n][n]

解法二：程序员面试金典中的解法 O(n ^ 2)

找出以元素i结尾的最长递增子序列

A[i] 结尾的最长子序列可以通过检查先前全部解法得出，只要将A[i]附加到最长并且有效，有效指 A[i]大于先前解法的最后一个数

    # 动态规划 O(n ^ 2), 而且有结果集
    def getHeight(self, men, n):
        if n < 1:
            return 0

        dps = [[men[0]]]

        for i in range(1, n):
            maxOrder = [men[i]]
            for dp in dps:
                if dp[-1] < men[i] and len(dp) >= len(maxOrder):
                        maxOrder = dp + [men[i]]
            dps.append(maxOrder)

        return len(max(dps, key=lambda a: len(a)))

思路三：动态规划 O(n ^ 2)

dp[i] 表示必须以i 元素结尾的最长递增子序列的长度，如何得出这个长度呢？

dp[i] 等于 men[0..i - 1]中比men[i]小的元素对应的dp值 + 1

    # 动态规划 O(n^2)
    def getHeight(self, men, n):
        # dp[i]表示已第i个元素结尾的最长递增子序列的长度
        dp = [0] * n
        dp[0] = 1
        lgst = 0
        for i in range(1, n):
            slgst = 0
            sidx = 0
            # 找到 men[0..i-1]中比men[i]小的对应的dp中的最大值
            while sidx < i:
                if men[sidx] <= men[i]:
                    slgst = slgst if slgst > dp[sidx] else dp[sidx]
                sidx += 1
        	dp[i] = slgst + 1
            lgst = dp[i] if dp[i] > lgst else lgst
        return lgst

思路四：最快的一种 O(nlogn)

动态规划，利用一个help数组，help[j] 代表的是遍历到此时刻如i, 长度为j + 1的最长递增子序列的最小末尾是什么。这是重点

深入理解看这里

http://v.qq.com/x/page/x0161lw32lr.html

    # 动态规划 O(nlogn)
    def getHeight(self, men, n):
        dp = [0] * n
        dp[0] = 1
        bs = [0] * n
        bs[0] = men[0]
        
        # 在bs中找到第一个比x大的数并替换
        def binary_search(x, end):
            i = 0
            j = end
            
            while i <= j:
                mid = (i + j) / 2
                if x > bs[mid]:
                    i = mid + 1
                else:
                    j = mid - 1
            end = max(end, i)
            bs[i] = x
            return i, end
            
        end = 0 # bs length
        for i in range(1, n):
            val, end = binary_search(men[i], end)
            dp[i] = val+1
        
        return max(dp)

编辑于 2016-08-08 20:04:31 回复(6)

L0L

 int getHeight(vector<int> men, int n) {
        vector<int> ret(n,1);
        ret[0]=1;
        int maxlen=1;
		for(int i=1;i<n;i++) {
			for(int j=i-1;j>=0;j--){
				if(men[i]>men[j])		ret[i]=max(ret[i],ret[j]+1);
			}
			maxlen=max(ret[i],maxlen);
		}
		return maxlen;
    }

发表于 2015-10-12 19:37:53 回复(2)

peter7788

看题目样例反而不懂题目意思了，结果4是怎么来的？结果不是[6,5,3]或者[6,5,4]的子序列应该是3么？

发表于 2015-08-29 20:45:59 回复(6)

Julius

//最长递增子序列问题，牛客7.29动态规划串讲第一题，看了视频模仿写出了O(nlogn)的解法
class Stack {
public:
    int getHeight(vector<int> men, int n) {
        // write code here
        int *dp = getDP(men, n);//记录以i为结尾的最长递增子序列
        int res = 0;
        for(int i = 0; i < n; ++i)
            res = max(res, dp[i]);
        return res;
    }
    
    int* getDP(vector<int> men, int n){//求dp数组的函数
        int *dp = new int[n];
        int *help = new int[n];//最长子序列为j+1时候，长度为j序列最小值
        help[0] = men[0];
        dp[0] = 1;
        int end = 0;//记录help数组有有效值的末尾
        int l = 0;
        int r = 0;
        for(int i = 1; i < n; ++i){//二分查找
            l = 0;
            r = end;
            while(l <= r){
                int mid = l + (r - l)/2;
                if(men[i] > help[mid])
                    l = mid + 1;
                else
                    r = mid - 1;
            }
            end = max(end, l);//l为第一个比men[i]大的数的位置
            help[l] = men[i];
            dp[i] = l + 1;
        }
        return dp;
    }
};

发表于 2015-10-08 23:37:50 回复(0)

marsforwill

搜dp 最长有序子序列

发表于 2015-07-19 08:57:52 回复(1)

此广告位出租

如果早些时间有投过阿里的简历的话，可能会做过摘桃子的那个题，和这题的意思一样，只是第一时间看了别人的动态规划做法，印象比较深，所以这次还是想到了这样做，虽然有更好的做法。

public class Stack {
    public int getHeight(int[] men, int n) {
        // write code here
        int[] res = new int[n];
		res[0] = 1;
		int max = 1;
		for (int i=1; i<n; i++){
			res[i] = 1;
			for (int j=i-1; j>=0; j--){
				if (men[i] > men[j] && res[j]+1 > res[i]){
					res[i] = res[j] + 1;					
				}
			}	
			max = Math.max(res[i], max);
		}
		return max;
    }
}

发表于 2017-08-23 10:43:50 回复(1)

ID84848484

import java.util.*;

public class Stack {
    public int getHeight(int[] men, int n) {
        // write code here
        //最长递增子序列
//以men[I]为结尾数字，通过前向扩展求其的最长递增子序列个数
        if(n<=0)
            return 0;
        int ret[]=new int[n];
        int ans=0;
        for(int i=0;i<n;i++){
            ret[i]=1;
            for(int j=0;j<i;j++){
                if(men[i]>men[j])
                    ret[i]=Math.max(ret[j]+1,ret[i]);
            }
            ans=Math.max(ans,ret[i]);
        }
        return ans;
    }
}

发表于 2019-06-01 15:48:07 回复(0)

C/C++

nbgao

class Stack {
public:
    int getHeight(vector<int> men, int n) {
        int dp[n],Max=0;
        fill(dp,dp+n,1);
        for(int i=1;i<n;i++){
            for(int j=i-1;j>=0;j--){
                if(men[i]>men[j])
                    dp[i] = max(dp[i], dp[j]+1);             }
            Max = max(Max, dp[i]);         }
        return Max;        
    }
};

发表于 2019-03-08 01:33:22 回复(0)

C/C++

Cavs

题目搞错了应该……先来的人在下面，所以是最长递减子序列问题，把下面的判断身高的改成>即可。
class Stack {
public:
    int getHeight(vector<int> men, int n) 
    {
        int maxCount = 1;
        vector<int> dp(n, 1);
        for (int i = 1; i < n; ++i)
        {
            for (int j = 0; j < i; ++j)
                if (men[j] < men[i]) dp[i] = max(dp[i], dp[j] + 1);
            maxCount = max(maxCount, dp[i]);
        }

        return maxCount;
    }
};

发表于 2017-06-29 19:08:57 回复(0)

Aurora1

class Stack:
    def getHeight(self, men, n):
        k = [0] * n
        for i in range(n):
            t = 0
            for j in range(i - 1, -1, -1):
                if men[i] > men[j] and k[j] > t:
                    t = k[j]
            k[i] = t + 1
        return max(k)

编辑于 2017-03-03 21:44:37 回复(0)

ThreeOrange

为什么是递增子序列，不应该是递减子序列吗？？

发表于 2016-09-05 16:41:40 回复(4)

Pis

class Stack { public: int getHeight(vector<int> men, int n) { // write code here  if(n == 0) return 0;  vector<int>dp;  dp.resize(men.size());  dp[0] = 1;   int max_res = -1;  //前面数字是否有小于当前数字的标志，初始为false  bool flag = false;  for (int i = 1; i < n; ++i) { int max_now = -1;  int now = men[i];  for (int j = i; j > 0; j--) { if(now > men[j-1]) {
                    flag = true;  max_now = max(max_now, dp[j-1]);  }
            } //有比当前值小的数，找到最大的数对应的dp+1  if(flag)
                dp[i] = max_now + 1;  //最小的，dp =1  else  dp[i] = 1;  flag = false;  max_res = max(max_res,dp[i]);  } return max_res;  }
};

发表于 2016-09-05 10:01:20 回复(0)

简单的快乐

import java.util.*;

public class Stack {

public int getHeight(int[] men, int n) {

/**

* 实质就是最长自增子序列，大致有两种方法

* 法一：

* 用排序后的数组和原来的数组进行比较，求最长公共子序列

* dp[m][n]表示数组x长度m与排序数组y长度n的最长公共子序列的长度

* 初始dp[0][0]=0，其中有一个为0 的时候；

* dp[i][j]=max{dp[i-1][j],dp[i][j-1]}, 如果x[i]!=y[j]

* dp[i][j]=dp[i-1][j-1]+1,如果x[i]=y[j];

// 法一：

int[] old=Arrays.copyOfRange(men, 0, n);

//System.arraycopy(men, 0, old, 0, n);

Arrays.sort(men);

int[][]dp=new int[n+1][n+1];//数组从0 开始，但是人数是从1开始

for(int i=1;i<=n;i++){

for(int j=1;j<=n;j++){

if(men[i-1]==old[j-1]){

dp[i][j]=dp[i-1][j-1]+1;

}else{

dp[i][j]=Math.max(dp[i-1][j], dp[i][j-1]);

}

return dp[n][n];*/

/**

* 法二：

* 动态规划

* dp[i]宝表示以表示以ai为元素的最长递增序列的长度,最后找出最大的dp[i]即可

int []dp=new int[n];//存储index为i的位置元素ai为为元素的最长递增序列的长度

int max=0;

for(int i=0;i<n;i++){

dp[i]=1;//假定没有，就是一个

for(int j=0;j<i;j++){

//找到j<i且aj<ai的值的最大值

if(men[j]<men[i]&&dp[j]>dp[i]-1)

dp[i]=dp[j]+1;

}

if(dp[i]>max){

max=dp[i];//最大值

}

return max;

}

发表于 2016-07-14 20:16:33 回复(0)

Ron

    public int getHeight(int[] men, int n) {
        // write code here
    	if(men == null){
    		return 0;
    	}
    	int[] dp = new int[n];
    	dp[0] = 1;
    	for(int i = 1; i < n; i++){
            dp[i] = 1;
    		for(int j = i-1; j >= 0; j--){
    			if(men[i] >= men[j] && dp[j]+1 > dp[i]){
    				dp[i] = dp[j] + 1;
    			}
    		}
    	}
    	int max = 0;
    	for(int i = 0; i < n; i++){
    		if(max < dp[i]){
    			max = dp[i];
    		}
    	}
    	return max;
    }

发表于 2016-06-11 15:38:32 回复(0)

Python

nothing_nothing

# -*- coding:utf-8 -*-
# python2.7, time:32ms, memory:5752K

class Stack:
    def getHeight(self, men, n):
        # write code here
        if n<=1:
            return n
        arr=[men[0]]
        maxlen=0
        for v in men[1:]:
            l,r=0,maxlen
            res_idx=-1
            while l<=r:
                mid=int((l+r)/2)
                if arr[mid] >= v:
                    r = mid - 1
                else:
                    res_idx = max(res_idx, mid)
                    l = mid + 1
            if res_idx !=-1:
                if len(arr)<=res_idx+1:
                    arr.append(v)
                else:
                    arr[res_idx+1]=min(arr[res_idx+1], v)
            else:
                arr[0]=min(arr[0],v)
            maxlen = len(arr)-1
        return maxlen+1

求最长上升子序列即可. n*logn时间复杂度. arr[i]维护长度为i+1的最长上升子序列最大元素(即末尾元素)的最小值. arr为单调数组可进行二分查找.

发表于 2020-07-10 23:05:15 回复(0)

C/C++

codewind

class Stack {
public:
    int getHeight(vector<int> men, int n) {
        // write code here
         
        vector<int> dp(n+1,1);
        int res = 0;
        for(int i=0;i<n;++i) {
            for(int j=0;j<i;++j) {
                if(men[j]<men[i]) {
                    dp[i] = max(dp[i],dp[j]+1);
                }
                res = max(dp[i],res);
            }
        }
        return res;
        
    }
};

发表于 2021-01-30 13:15:14 回复(0)

TankWitch

class Stack {
public:
    int getHeight(vector<int> men, int n) {
        // write code here
        memset(dp, 0, sizeof(dp));
        dp[0] = 1;
        for (int i = 1; i < n; ++i) {
            dp[i] = 1;
            for (int j = 0; j < i; ++j) {
                if (men[j] < men[i] && dp[j] + 1 > dp[i]) {
                    dp[i] = dp[j] + 1;
                }
            }
        }
        int ret = 0;
        for (int i = 0; i < n; ++i) {
            ret = max(ret, dp[i]);
        }
        return ret;
    }
private:
    int dp[503] = {0};
};

发表于 2020-07-23 13:41:16 回复(0)

南少201911241210480

class Stack {
public:
    int getHeight(vector<int> men, int n) {
        // write code here
        vector<int>a{men[0]};
        int k=0;
        for(int i=1;i<n;i++)
        {
           int l=0,r=k;
           while(l<=r)
           {
               int m=(l+r)/2;
               if(a[m]>=men[i])
                   r=m-1;
               else
                   l=m+1;
           }
            if(l>k)a.push_back(men[i]),k++;
            else a[l]=men[i];
        }
        return k+1;
    }
};
直接二分找到第一个比它大的替换，找不到加末尾，结果就是维护的二分查找数组的大小

发表于 2020-04-19 14:06:15 回复(0)