定义二叉树节点如下：
public class Node{
public int value;
public Node left;
public Node right;
public Node (int data){
this.value = data;
}
}
一个数组的MaxTree定义如下：
数组必须没有重复元素，MaxTree是一棵二叉树，数组的每一个值对应一个二叉树的节点，包括MaxTree树在内且在其中的每一棵子树上，值最大的节点都是树的头。给定一个没有重复元素的数组arr，写出生成这个数组的MaxTree的函数，要求如果数组长度为N，则时间复杂度为O(N),额外空间复杂度为O(N)
思路：找一个数左边离它最近的比它大的，还有右边一个比他大的，即可实现MaxTree。建立一个大底栈，对于任何一个数，当它从栈中弹出时，当前将要入栈的数是弹出的数的右边离他最近的比他大的数，而它栈中下面的数是离他最近的左边比他大的数
2.最大值减去最小值小于或等于num的子数组数量
给定数组arr和整数num，共返回有多少个子数组满足以下情况：
max(arr[i...j]) - min(arr[i...j]) <= num
max(arr[i...j])表示子数组arr[i...j]中的最大值，min（arr[i...j]）表示子数组arr[i...j]中的最小值
要求：如果数组长度为N，求实现时间复杂度为O(N)的解法
建立一个双端队列，用于求出最大值和最小值，有两个指针，都从数组头开始向右滑动，维持一个递增的队列，此队列中存储的是数组的下标。如果队列右边比现在队尾小的话，依次将队列中的尾部从右弹出，直到可以将当前值右侧入队。
当队列右边界在向右移动时，队列中的最大值只可能越来越小，左边界在向右移动时，队列中的最小值越来越大。
public static int getNum(int[] arr, int num){
if(arr == null || arr.length == 0){
return 0;
}
LinkedList<Integer> qmin = new LinkedList<Integer>();
LinkedList<Integer> qmax = new LinkedList<Integer>();
int i = 0;
int j = 0;
int res = 0;
while(i < arr.length){
while(j < arr.length){
while(!qmin.isEmpty() && arr[qmin.peekLast()] >= arr[j]){
qmin.pollLast();
}
qmin.adList(j);
while(!qmax.isEmpty() && arr[qmax.peekLast()] <= arr[j]){
qmax.polLast();
}
qmax.addLast(j);
if(arr[qmax.getFirst()] - arr[qmin.getFirst()] > num){
break;
}
j++;
}
if(qmin.peekFirst() == i){
qmin.pollFirst();
}
res += j - i;
i++;
}
return res;
}
3.环形单链表的约瑟夫问题
41个人围成一个环，由第一人开始报数，报到3的人即自杀，然后再由下一任重新报1，报到3的人再自杀，依次类推，直到剩下最后一个人。现用单向环形链表描述该结构并呈现整个自杀过程
输入：一个环形单向链表的头节点head和报数的值m
返回：最后生存下来的节点，且这个节点自己组成环形单向链表，其他节点都删除
要求：如果链表节点数为N，实现时间复杂度为O(N)的解法
public static Node josephusKill(Node head, int m){
if(head == null || head.next == head || m < 1){
return head;
}
Node cur = head.next;
int tmp = 1; //ListSize
while(cur != head){
tmp++;
cur = cur.next;
}
tmp = getLive(tmp, m);
while(--tmp != 0){
head = head.next;
}
head.next = head;
return head;
}
public static int getLive(int i, int m){
if(i == 1){
return 1;
}
return (getLive(i - 1, m) + m - 1) % i + 1;
}
public static void printCircularList(Node head){
if(head == null){
return;
}
}