对于一个没有重复元素的整数数组，请用其中元素构造一棵MaxTree，MaxTree定义为一棵二叉树，其中的节点与数组元素一一对应，同时对于MaxTree的每棵子树，它的根的元素值为子树的最大值。现有一建树方法，对于数组中的每个元素，其在树中的父亲为数组中它左边比它大的第一个数和右边比它大的第一个数中更小的一个。若两边都不存在比它大的数，那么它就是树根。请设计O(n)的算法实现这个方法。 给定一个无重复元素的数组A和它的大小n，请返回一个数组，其中每个元素为原数组中对应位置元素在树中的父亲节点的编号，若为根则值为-1。 测试样例： [3,1,4,2],4 返回：[2,0,-1,2] 要求时间复杂度为O(n),题目中已经有提示了，其实和最大最小堆有一点相似，对于大顶堆，我们常用树的方式理解，但是实际上可以用线性表存储（即数组），因此它需要是一棵完全二叉树（中间不能缺节点）。本题中的MaxTree只要求是二叉树就行了~，限制少一些，所以构建的时间复杂度也比建立大顶堆低一些。（大根堆构建初堆的时间复杂度也是O(n)) 利用栈可以快速找出左边和右边第一个比它大的值。
class MaxTree {public: vector<int> buildMaxTree(vector<int> A, int n) { vector<int> res(n,0); vector<int> vecleft(n,0); vector<int> vecright(n,0); stack<int> mystack; stack<int> mystackright; int i=0; while(i!=n) { if(mystack.empty()) { mystack.push(i); vecleft[i]=-1; ++i; } else if(A[i]<A[mystack.top()]){ vecleft[i]=mystack.top(); mystack.push(i); ++i; } else { mystack.pop(); } } i=n-1; while(i!=-1) { if(mystackright.empty()) { mystackright.push(i); vecright[i]=-1; --i; } else if(A[i]<A[mystackright.top()]){ vecright[i]=mystackright.top(); mystackright.push(i); --i; } else { mystackright.pop(); } } for(int i=0;i!=n;++i) { if(vecleft[i]==-1&&vecright[i]==-1) res[i]=-1; else if(vecleft[i]==-1&&vecright[i]!=-1) res[i]=vecright[i]; else if(vecleft[i]!=-1&&vecright[i]==-1) res[i]=vecleft[i]; else if(A[vecleft[i]]<A[vecright[i]]) res[i]=vecleft[i]; else res[i]=vecright[i]; } return res; }};新闻热点
疑难解答
