对于一个没有重复元素的整数数组，请用其中元素构造一棵MaxTree，MaxTree定义为一棵二叉树，其中的节点与数组元素一一对应，同时对于MaxTree的每棵子树，它的根的元素值为子树的最大值。现有一建树方法，对于数组中的每个元素，其在树中的父亲为数组中它左边比它大的第一个数和右边比它大的第一个数中更小的一个。若两边都不存在比它大的数，那么它就是树根。请证明这个方法的正确性，同时设计O(n)的算法实现这个方法。
给定一个无重复元素的数组A和它的大小n，请返回一个数组，其中每个元素为原数组中对应位置元素在树中的父亲节点的编号，若为根则值为-1。
[3,1,4,2],4
返回：[2,0,-1,2]
import java.util.*;
public class MaxTree {
public int[] buildMaxTree(int[] A, int n) {
// write code here
if (n < 1) {
return new int[0];
}
if (n == 1) {
return new int[]{-1};
}
int[] parentArr = new int[n];
int i;
for (i = 0; i < A.length; i++) {
int leftLargerIdx = findFirstLargerIdx("left", A, i);
int rightLargerIdx = findFirstLargerIdx("right", A, i);
if (leftLargerIdx != -1 && rightLargerIdx != -1) {
if (A[leftLargerIdx] < A[rightLargerIdx]) {
parentArr[i] = leftLargerIdx;
} else {
parentArr[i] = rightLargerIdx;
}
} else {
if (leftLargerIdx != -1) {
parentArr[i] = leftLargerIdx;
} else if (rightLargerIdx != -1) {
parentArr[i] = rightLargerIdx;
} else {
parentArr[i] = -1;
}
}
}
return parentArr;
}
private int findFirstLargerIdx(String direction, int[] A, int currIdx) {
int step = direction == "left" ? -1 : 1;
int firstLargerIdx = -1;
for (int i = currIdx; direction == "left" ? i >= 0 : i < A.length; i = i + step) {
if (A[i] > A[currIdx]) {
firstLargerIdx = i;
break;
}
}
return firstLargerIdx;
}
}
};
import java.util.*;
public class MaxTree {
public int[] buildMaxTree(int[] arr, int n) {
int []res=new int[n];
for(int index=0 ;index <n ;index++){
int left=index,right=index;
//往左边找到第一个比当前数大的。
for(int i=index-1 ; i>=0 ;i--){
if(arr[i]>arr[index]){
left=i;
break;
}
}
//往右边找到第一个比当前数大的。
for(int j=index+1 ;j<n ;j++){
if(arr[j]>arr[index]){
right=j;
break;
}
}
//数组中值最大者作为根节点
if(left==index&&right==index)
res[index]=-1;
else if (left==index) {
res[index]=right;
}else if (right==index) {
res[index]=left;
}else {
//选left和right中较小者作为当前节点的父亲节点
if(arr[left] < arr[right])
res[index]=left;
else
res[index]=right;
}
}
return res;
}
}
class MaxTree {
public:
vector<int> buildMaxTree(vector<int> A, int n) {
vector<int> result;
stack<int> s;
if(n<=0)
return vector<int>();
for(int i=0;i<n;i++) { int p = -1; while(!s.empty() && A[i]>A[s.top()]) { int t = s.top(); s.pop(); if(result[t]==-1 || A[i] < A[result[t]]) result[t] = i; } if(!s.empty()) p = s.top(); s.push(i); result.push_back(p); } return result;
}
};
# -*- coding:utf-8 -*- class MaxTree: def buildMaxTree(self, A, n): # write code here if n<1: return None if n==1: return [-1] num=[] for i in range(n): j=i find_left=False left=0 while j>0 and not find_left: j-=1 if A[j]>A[i]: find_left=True left=A[j] k=i find_right=False right=0 while k<n-1 and not find_right: k+=1 if A[k]>A[i]: find_right=True right=A[k] node_root=-1 if left>right and find_left and find_right: node_root=k elif left<right and find_left and find_right: node_root=j elif find_right and not find_left: node_root=k elif not find_right and find_left: node_root=j elif not find_right and not find_left: node_root=-1 num.append(node_root) return num
vector<int> buildMaxTree(vector<int> A, int n) {
if (n <= 0){
return vector<int>();
}
vector<int> res; // 数组元素在树中父亲节点的编号
stack<int> s; // 栈 以递减方式存放元素值的位置index
for (int i = 0; i < n; ++i){
int pos = -1; // 根编号为-1
// 当前访问的元素比栈顶大 栈中元素需要出栈
while(!s.empty() && A[i] > A[s.top()]){
int tmp = s.top();s.pop();
if (res[tmp] == -1 || A[i] < A[res[tmp]]){
res[tmp] = i;
}
}
// 找到了最近的比A[i]大的数
if (!s.empty()){
pos = s.top();
}
s.push(i);
res.push_back(pos);
}
return res;
}
理解题目：题目中“原数组中对应位置元素在树中的父亲节点的编号”这句话中，把"编号"换成"索引"更好理解。意思为找到当前元素的父节点在原数组中的索引。
比如题目中的‘1’，左边第一个比它大的是‘3’，右边第一个比它大的是‘4’，那么它的父节点就是‘3’，父节点的索引就是0。以此类推得出其他元素父节点的索引，作为返回结果。
解题思路：维持两个数组，一个保存每个元素左边第一个比自己大的数的下标（注意要保存的是下标），另一个保存右边的，如果没有，自己就是最大的，那么保存-1；
如题目中的例子：
原数组： 3 1 4 2
lp： -1 0 -1 2
rp： 2 2 -1 -1
然后依次比较左数组和右数组；如果一个是-1，一个大于等于0，那么说明-1的那一边没有比该元素更大的数了，他的父亲就是大于等于0的那个数；如果两个数都大于等于0，那么依据题目中的意思，把数值更小的作为父亲，此时就要比较一下两个下标在原数组中对应的数值；如果两个都为-1，说明这个数就是原数组中最大的了，这个元素就是根节点，刚好我们也保存为-1，和题目要求一致，所以就不做操作了。
如何构建lp和rp？原数组从左向右扫一次构建lp。从右向左扫一次构建rp。
为什么要用栈？因为题目中构建树的要求是，找到左边或右边第一个比自己大的，也就是找左边或右边离自己最近的那个比自己大的。假设我们现在从左向右扫，每扫一个，就要向我们的栈中加入被扫元素的索引。这样我们在进行比较索引的对应值的大小的时候，因为我们是从栈顶取，所以拿到的总是那个最后被我们加入进栈的，最后加入的，也就是离我们当前这个最近的。
vector<int> buildMaxTree(vector<int> A, int n) {
if(n<=0) return vector<int>();
vector<int>res(n,-1);
vector<int>lp(n,-1);
vector<int>rp(n,-1);
//用栈是为了存储（距离当前元素左边或者右边）最近的元素的下标
stack<int>s;
for(int i=0;i<n;i++){
//找出值小于A[i]的下表
while(!s.empty() && A[i]>A[s.top()])
s.pop();
//如果s都在上一步被弹出光了，就说明左边没有比当前元素大元素 所以用默认的-1
if(!s.empty())
lp[i]=s.top();
s.push(i);
}
while(!s.empty()) s.pop();
//rp同理
for(int i=n-1;i>=0;i--){
while(!s.empty() && A[i]>A[s.top()])
s.pop();
if(!s.empty())
rp[i]=s.top();
s.push(i);
}
for(int i=0;i<n;i++){
if(lp[i]>=0 && rp[i]>=0)
res[i]=A[lp[i]]>=A[rp[i]]?rp[i]:lp[i];
if(lp[i]>=0&&rp[i]==-1){
res[i]=lp[i];
}
else if(rp[i]>=0&&lp[i]==-1){
res[i]=rp[i];
}
}
return res;
}
class MaxTree {
public:
vector<int> buildMaxTree(vector<int> A, int n) {
// write code here
// 单调栈
vector<int>v1(n,-1);
vector<int>v2(n,-1);
vector<int>height;
for(int i=0;i<n;++i)
{
while(!height.empty()&&A[height.back()]<A[i])
{
v1[height.back()] = i;
height.pop_back();
}
height.push_back(i);
}
while(!height.empty()) height.pop_back();
for(int i=n-1;i>=0;--i)
{
while(!height.empty()&&A[height.back()]<A[i])
{
v2[height.back()] = i;
height.pop_back();
}
height.push_back(i);
}
vector<int>ans(n,-1);
for(int i=0;i<n;++i)
{
if(v1[i]!=-1&&v2[i]!=-1)
ans[i] = A[v1[i]]<A[v2[i]] ? v1[i] : v2[i];
else{
if(v1[i]!=-1) ans[i] = v1[i];
else ans[i]=v2[i];
}
}
return ans;
}
};
# -*- coding:utf-8 -*-
class MaxTree:
def buildMaxTree(self,A, n):
# write code here
list1=[0]*n
for i in range(n):
max1=''
max2=''
if len(A[0:i])!=0:
for j in A[i-1::-1]:
if j>A[i]:
max1=j
break
if len(A[i+1:])!=0:
for k in A[i+1:]:
if k>A[i]:
max2=k
break
if max1=='' and max2!='':
list1[i]=A.index(max2)
elif max2=='' and max1!='':
list1[i]=A.index(max1)
elif max1=='' and max2=='':
list1[i]=-1
else:
list1[i]=A.index(min(max1,max2))
return list1
# -*- coding:utf-8 -*- class MaxTree: def buildMaxTree(self, A, n): if n<1: return None if n==1: return [-1] num=[] for i in range(n): j=i find_left=False left=0 while j>0 and not find_left:#找到左边的第一个比它大的数 j-=1 if A[j]>A[i]: find_left=True left=A[j] k=i find_right=False right=0 while k<n-1 and not find_right:#找到右边的第一个比它大的数 k+=1 if A[k]>A[i]: find_right=True right=A[k] node_root=-1 if find_left and find_right:#左右都能找到，则取较小数的下标 node_root=A.index(min(left,right)) elif find_right or find_left:#只在一边找到，则取该方向的下标 node_root=A.index(max(left,right)) else:#两边都没找到，则为根节点 node_root=-1 num.append(node_root) return num
import java.util.*;
public class MaxTree {
public int[] buildMaxTree(int[] A, int n) {
// write code here
if( n <= 0){
return null;
}
int[] leftPosition = new int[n];
int[] rightPosition = new int[n];
int[] result = new int[n];
Stack<Integer> stack = new Stack<Integer>();
for(int i =0; i < n; i++){
leftPosition[i] = -1;
rightPosition[i] = -1;
result[i] =-1;
}
for(int i =0; i < n;i++){
while(!stack.empty()&& A[i] > A[stack.peek()]){
stack.pop();
}
if(!stack.empty()){
leftPosition[i] = stack.peek();
}
stack.push(i);
}
while(!stack.empty()){
stack.pop();
}
for(int i =n-1; i>=0;i--){
while(!stack.empty()&& A[i] > A[stack.peek()]){
stack.pop();
}
if(!stack.empty()){
rightPosition[i] = stack.peek();
}
stack.push(i);
}
for(int i =0; i < n; i++){
if(leftPosition[i]>=0 && rightPosition[i] >=0){
result[i] = A[leftPosition[i]] >= A[rightPosition[i]]? rightPosition[i]:leftPosition[i];
}
if(leftPosition[i] >=0 && rightPosition[i] == -1)
result[i] = leftPosition[i];
if(rightPosition[i] >=0 && leftPosition[i] == -1)
result[i] = rightPosition[i];
}
return result;
}
}
left[i]表示第i个元素的左边第一个比它小的数的下标。
right[i]表示第i个元素的右边的第一个比它小的数的下标。
public int[] buildMaxTree(int[] A, int n) {
int[] left=new int[n];
left[0]=0;
for(int i=1;i<n;i++) {
int x=i-1;
while(A[i]>=A[x]) {
if(x==left[x])break;
x=left[x];
}
if(A[i]<A[x])left[i]=x;
else left[i]=i;
}
int[] right=new int[n];
right[n-1]=n-1;
for(int i=n-2;i>=0;i--) {
int x=i+1;
while(A[i]>=A[x]) {
if(x==right[x])break;
x=right[x];
}
if(A[i]<A[x])right[i]=x;
else right[i]=i;
}
int[] d=new int[n];
for(int i=0;i<n;i++) {
if(left[i]==i||right[i]==i) d[i]=(left[i]==i)?right[i]:left[i];
else d[i]=A[left[i]]<=A[right[i]]?left[i]:right[i];
if(d[i]==i)d[i]=-1;
}
return d;
}
class MaxTree {
public:
vector buildMaxTree(vector A, int n) {
// write code here
vector pos(n);
for(int i=0; i<n; i++)
{
int left_max = INT_MAX;
int right_max = INT_MAX;
int parent;
int j, k;
for(j=i+1; j<n; j++)
if(A[j]>A[i])
{
right_max = A[j];
break;
}
for(k=i-1; k>=0; k--)
if(A[k]>A[i])
{
left_max = A[k];
break;
}
if(left_max>right_max)
pos[i] = j;
else if(left_max<right_max)
pos[i] = k;
else
pos[i] = -1;
}
return pos;
}
};
import java.util.*;
public class MaxTree {
public int[] buildMaxTree(int[] A, int n) {
// write code here
if(n<=1){
return new int[]{-1};
}
int[] res = new int[n];
//用两哈希表分别保存当前数字左右两边边第一个大数
HashMap<Integer,Integer> leftMap = new HashMap<>();
HashMap<Integer,Integer> rightMap = new HashMap<>();
Stack<Integer> stack = new Stack<>();
//用一个哈希表保存对应元素在数组中的下标
HashMap<Integer,Integer> indexMap = new HashMap<>();
//从左到右遍历，找到每个数的左边第一个大数
for(int i=0; i<n; i++){
int cur = A[i];
indexMap.put(cur,i);//保存元素在数组中的下标
while(!stack.empty() && stack.peek()<cur){
getFirstMax(stack, leftMap);
}
stack.push(cur);
}
while(!stack.empty()){
getFirstMax(stack, leftMap);
}
//从右到左遍历，找到每个数的右边第一个大数
for(int i=n-1; i>=0; i--){
int cur = A[i];
while(!stack.empty() && stack.peek()<cur){
getFirstMax(stack, rightMap);
}
stack.push(cur);
}
while(!stack.empty()){
getFirstMax(stack, rightMap);
}
//构建二叉树
for(int i=0; i<n; i++){
int cur = A[i];
int left = leftMap.get(cur);
int right = rightMap.get(cur);
if(left==Integer.MAX_VALUE && right==Integer.MAX_VALUE){
res[i] = -1;
}else{
int parent = left<right?left:right;
res[i] = indexMap.get(parent);
}
}
return res;
}
public void getFirstMax(Stack<Integer> stack, HashMap<Integer,Integer> map){
int node = stack.pop();
if(stack.empty()){
map.put(node,Integer.MAX_VALUE);
}else{
map.put(node,stack.peek());
}
}
}
//根据左程云算法书
public static int[] getMaxTree(int[] A,int n){
int[] res=new int[n];
Stack stack=new Stack();//栈中始终保持栈底到栈顶从大到小的顺序。栈中存放的是在原数组下标值。
HashMap lbignode=new HashMap();//用map存放左边比当前元素大的第一个元素在数组中的下标值
HashMap rbignode=new HashMap();
for(int i=0;i!=n;i++){ //对数组A正向检查一遍
int curnNode=A[i];
while(!stack.isEmpty()&&A[stack.peek()]<curnNode){
popStackSetMap(A,stack, lbignode);//若待入栈元素比栈顶元素大，则将栈顶节点弹出，同时栈顶元素的下一个即为栈顶元素左边第一个比栈顶元素大的节点。
}
stack.push(i);
}
while(!stack.isEmpty()){
popStackSetMap(A,stack, lbignode);
}
for(int j=n-1;j!=-1;j--){//逆向检查一遍
int curnNode=A[j];
while(!stack.isEmpty() && A[stack.peek()]<curnNode){
popStackSetMap(A,stack, rbignode);//若当前节点比栈顶节点大，则将栈顶节点弹出，同时栈顶元素的下一个即为栈顶元素右边第一个比栈顶元素大的节点。
}
stack.push(j);
}
while(!stack.isEmpty()){
popStackSetMap(A,stack, rbignode);
}
for(int i=0;i<n;i++){
int key=A[i];
int leftNode=lbignode.get(key);//获得左边比当前元素大的元素下标
int rightNode=rbignode.get(key);// 获得右边比当前元素大的元素下标
if(leftNode==-1 && rightNode==-1)
res[i]=-1;
else if(leftNode==-1){
res[i]=rightNode;
}
else if(rightNode==-1){
res[i]=leftNode;
}
else{ int parent=A[leftNode]<A[rightNode]?leftNode:rightNode;作为父节点下标
res[i]=parent;
}
}
return res;
}
public static void popStackSetMap(int[] arr,Stack stack,HashMap map){
int node=stack.pop();
if(stack.isEmpty()){//若为栈底元素，则表示左边没有比其更大的数。
map.put(arr[node], -1);
}
else {
map.put(arr[node], stack.peek());//将数组中的值及比该值大的第一个数的数组下标放入map中
}
}
测试通过
使用栈，使得时间复杂度为O(N)
import java.util.*;
public class MaxTree {
public int[] buildMaxTree(int[] A, int n) {
// write code here
if(A==null||A.length==0) return new int[0];
int[] res=new int[A.length];
Stack<Integer> s=new Stack<Integer>(); //用来存放下标
int[] left=new int[A.length];//放的是下标
for(int i=0;i<A.length;i++){
int cur=A[i];
if(s.isEmpty()||A[s.peek()]>cur){
if(s.isEmpty()){
left[i]=-1;//下标不可能是-1，所以用-1来表示该数不存在右边一个大的值
}else{
left[i]=s.peek();
}
s.push(i);//放的是下标
}else{
while(!s.isEmpty()&&A[s.peek()]<cur){
s.pop();
}
left[i]=s.isEmpty()?-1:s.peek();//【注意】此时可能出现也被移除空了的情况，所以也要再判断一下
s.push(i);
}
}
s.clear();//清空之后再用这个stack
int[] right=new int[A.length];
for(int i=A.length-1;i>=0;i--){//从右往左遍历，找出该下标下的左边第一个大于该数的下标
int cur=A[i];
if(s.isEmpty()||A[s.peek()]>cur){
right[i]=s.isEmpty()?-1:s.peek();//right数组中也是从右往左放
s.push(i);//放的是下标
}else{
while(!s.isEmpty()&&A[s.peek()]<cur){
s.pop();
}
right[i]=s.isEmpty()?-1:s.peek();
s.push(i);
}
}
for(int i=0;i<A.length;i++){
if(left[i]==-1&&right[i]==-1){
res[i]=-1;
}else if(left[i]==-1||right[i]==-1){
res[i]=left[i]==-1?right[i]:left[i];
}else{
res[i]=A[left[i]]<A[right[i]]?left[i]:right[i];//取两个中对应a中的数值较小的那个
}
}
return res;
}
}
class MaxTree {
public:
vector<int> buildMaxTree(vector<int> A, int n) {
// write code here
stack<int> stack_;
vector<int> ans(n);
for (int i = 0; i < n; i++) {
while (!stack_.empty()) {
if (A[stack_.top()] > A[i]) {
ans[i] = stack_.top();
stack_.push(i);
break;
}
else {
stack_.pop();
}
}
if (stack_.empty()) {
stack_.push(i);
ans[i] = -1;
}
}
while (!stack_.empty()) {
stack_.pop();
}
for (int i = n - 1; i >= 0; i--) {
while (!stack_.empty()) {
if (A[stack_.top()] > A[i]) {
if (ans[i] == -1) {
ans[i] = stack_.top();
}
else {
if (A[ans[i]] > A[stack_.top()]) {
ans[i] = stack_.top();
}
}
stack_.push(i);
break;
}
else {
stack_.pop();
}
}
if (stack_.empty()) {
stack_.push(i);
}
}
return ans;
}
};
思路来源：左程云老师讲解的构造maxtree，栈的应用。
扫描二维码，关注牛客网
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
京公网安备
11010502036488号
