构造数组的MaxTree

题目

给定一个没有重复元素的数组,写出生成这个数组的MaxTree函数,如果数组长度为N,要求时间复杂度为O(n),额外的空间复杂度为O(N)。

以下列原则建立这棵树:

  • 每一个数的父节点是它左边第一个比它大的数和它右边第一个比它大的数中较小的那个
  • 如果一个数左边没有比它大的数,右边也没有,这个数是这个数组的最大值,即为MaxTree的头结点

如[3,4,5,1,2]

        5
      /  \
     4    2
    / \
   3   1 

伪代码:

以[3,1,2]为例
public Node getMaxTree(int[] arr){
    //先从左往右遍历找每个数左边第一个比它大的数,栈保持递减序列,若新入栈的数大于栈顶元素,栈顶元素出栈,left.put(出栈的元素,出栈后的栈顶元素)。类似,从右往左遍历,找每个数右边第一个比它大的数
    Stack<Node> stack = new Stack<Node>();

    //存储左边第一个比当前数大的数,如(1,3),栈底元素对应的为null,如(3,null)
    HashMap<Node,Node> left = new HashMap<Node,Node>()

    //存储右边第一个比当前数大的数,如(1,2),栈底元素对应的为null,如(3,null)
    HashMap<Node,Node> right = new HashMap<Node,Node>()

    //从两个HashMap中取数,从头到尾遍历,若一个数存在左边第一个大的数和右边第一个大的数取最小值。
}

生成数如下所示:
        3
      /
    2
   /
 1
Share