首页 > 代码库 > 待字闺中之相差最大分析
待字闺中之相差最大分析
题目来源，待字闺中，原创@陈利人 ，欢迎大家继续关注微信公众账号“待字闺中”
给定无序数组A，在线性时间内找到i和j，j>i，并且保证A[j]-A[i]是最大的。
这个题目是比较简单的。很直接的，对于每一个A[j]，如果知道前面的元素中最小的元素min，则此时相差最大为A[j]-min。则，假设有一个数组M，M[j]表示[0,j-1]中最小的元素。这个遍历一边A，就可以完成构造M。再遍历一边数组，就可以找到相差最大的。我们举个例子看看M，以及是否有改进的空间。
假设A={1,2,5,3,4}。通过一次遍历，得到M如下：
| 1 | 1 | 1 | 1 | 1 |
这是一个极端的例子，但确实给了我们一个改进的方向，就是并不需要一个数组保存最小值，而只需要一个变量即可。
上面的例子不明显，假定A={2,5,1,3,4}，过程如下：
| j | A[j] | 最小值m | A[j]-m |
| 0 | 2 | 2 | 0 |
| 1 | 5 | 2 | 3 |
| 2 | 1 | 1 | 0 |
| 3 | 3 | 1 | 2 |
| 4 | 4 | 1 | 3 |
最终得到相差最大为3.这个例子，可以找到两个i，j。
代码如下：
int maxDiff(vector<int>& data)
{
int length = data.size();
if(length <= 1)return 0;
int i,minValue = http://www.mamicode.com/data[0],res = numeric_limits::min();>
这个题目，如果有的同学给出数组C,C[j]表示[0,j]中的最小值；数组B表示[j+1, n-1]中的最大值；这两个数组遍历两次可以得到，然后，再遍历一次A，对于每一个i，B[i]-C[i]中最大的，就是最终的值。这个思路也是ok的，只不过比我们开始提到的，更加一些，可以通过观察C，B的变化，找到规律，进行化简。
待字闺中之相差最大分析
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。