寻找最长的严格递减数字序列_

推荐

NoNoNoNo

最有复杂度并不是看最简单的情况。分析如下：

建立标志数组，同原来数组

从最大的数开始寻找，四周，DFS，记录每次的最大长度。

因为每一次寻找至少可以消除自身，自身被标志为已访问。

如果能向任意一个方向走，那么任意一个方向的元素也可以被标志为已访问(用该元素的最大长度代替)。

也就是说，每个元素确实只要被找一次。

编辑于 2016-02-26 14:51:36 回复(2)

mopodao

动态规划+记忆化可以O(MN)

int dfs(x, y) { //从(x，y) 开始递减最长长度

if (f[x][y] != 0) return f[x][y]; //已经计算过的直接return答案 O(1)

f[x][y]=1;

for (4 个方向) {

if (a[x][y] > a[xx][yy]) f[x][y]=max(f[x][y], dfs(xx, yy) + 1);

}

return f[x][y];

}

void main() {

memset(f, 0, sizeof(f));

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

ans = max(ans, dfs(i, j));

}

虽然有两层for循环，但有些dfs(i,j)是O(1)的。每个点只被遍历一次后就记录下f[x][y]。

所以是O(M*N) + O(M*N) //dfs()总的复杂度+两层for的复杂度

发表于 2015-08-29 14:24:07 回复(4)

穆晨

此题只看结果，最优情况就是至少要把这m*n个数每个读一遍，所以最优就是O（m*n）

发表于 2015-08-24 12:26:40 回复(2)

董泽锋

对于矩阵的每个数mat[i][j]，如果mat[i][j]比它上下左右的某个数大，那么就可以建立一条mat[i][j]指向这个点的一条有向边，权值为1.

经过这个过程之后，就可以建立一幅图，原问题转换为求解这个图的最长简单路径。

先拓扑排序，时间复杂度O(V + E)，再动态规划O(V).由于这个图的每个点最多有4条出度边，所有总的时间复杂度就是O(V)，即O(m*n).

发表于 2016-09-09 16:27:16 回复(0)

许传炼

CDF可以排除,因为M,N具有轮换对称性,B太短绝对不可能,同理E太长也同样不可能

发表于 2016-09-03 19:01:36 回复(0)

王晓光子free

不考虑空间复杂度：对M*N的矩阵排序，并记录他们的位置，再从小打到遍历这个有序序列，根据位置信息判断能不能在矩阵中连接。时间复杂度为O(M*N)+O(M*N)

发表于 2015-08-24 22:32:13 回复(0)

努力搬砖的小学生

额，好晕

发表于 2016-11-11 21:10:03 回复(0)

不再做蜡笔小熊啦~

感觉此题应该给定各数的大小顺序，

这样可以从最小的数开始，深度优先搜索（DFS），记录搜索的最大长度，然后次小的数，

下一次搜索就可以直接使用已经搜索的结果+1

发表于 2016-06-03 14:14:23 回复(0)

ownfed

这道题可以这样考虑：采用DFS，T=O(e+v)，这里面的v是顶点数：v=MN，e是边，因为矩阵中，只有上下左右可到达，所以e=（M-1）（N-1）

发表于 2015-09-15 14:12:17 回复(0)

寻找最长的严格递减数字序列

问题信息

热门推荐

相关试题