首页 > 试题广场 >

构造MaxTree

[编程题]构造MaxTree
  • 热度指数:3693 时间限制:C/C++ 3秒,其他语言6秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解

对于一个没有重复元素的整数数组,请用其中元素构造一棵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 <= 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;
    }
}

编辑于 2018-09-21 21:27:42 回复(0)

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;
      }
发表于 2018-08-21 10:42:11 回复(0)

问题信息

难度:
2条回答 20746浏览

热门推荐

通过挑战的用户

查看代码
构造MaxTree