题目：
定义二叉树节点如下： public class Node { public int value; public Node left; public Node right;
public Node(int data) { this.value = data; } }一个数组的MaxTree定义如下
1 数组没有重复元素 2 MaxTree是一棵二叉树，数组的每一个值对应一个二叉树节点
3包括MaxTree树在内且其中的每一棵子树上，值 最大的节点都是树的头
给定一个没有重复元素的数组arr，写出生成这个数组的MaxTree函数，要求如果数组长度为N，则时间复杂度为O（N），额外空间复杂度为O（N）
public class MaxTree { /* * 节点类 */ public static class Node { public int value; public Node left; public Node right; public Node(int data) { this.value = data; } } public static Node getMaxTree(int[] arr) { Node[] nArr = new Node[arr.length]; for (int i = 0; i != arr.length; i++) { nArr[i] = new Node(arr[i]); } Stack<Node> stack = new Stack<Node>(); HashMap<Node, Node> lBigMap = new HashMap<Node, Node>();//存放节点对应的左边第一个比它大的节点 HashMap<Node, Node> rBigMap = new HashMap<Node, Node>();//存放节点对应的右边第一个比它大的节点 for (int i = 0; i != nArr.length; i++) { Node curNode = nArr[i]; while ((!stack.isEmpty()) && stack.peek().value < curNode.value) { popStackSetMap(stack, lBigMap); } stack.push(curNode); } while (!stack.isEmpty()) { popStackSetMap(stack, lBigMap); } for (int i = nArr.length - 1; i != -1; i--) { Node curNode = nArr[i]; while ((!stack.isEmpty()) && stack.peek().value < curNode.value) { popStackSetMap(stack, rBigMap); } stack.push(curNode); } while (!stack.isEmpty()) { popStackSetMap(stack, rBigMap); } Node head = null; for (int i = 0; i != nArr.length; i++) { Node curNode = nArr[i]; Node left = lBigMap.get(curNode); Node right = rBigMap.get(curNode); if (left == null && right == null) { head = curNode; } else if (left == null) { if (right.left == null) { right.left = curNode; } else { right.right = curNode; } } else if (right == null) { if (left.left == null) { left.left = curNode; } else { left.right = curNode; } } else { Node parent = left.value < right.value ? left : right; if (parent.left == null) { parent.left = curNode; } else { parent.right = curNode; } } } return head; } public static void popStackSetMap(Stack<Node> stack, HashMap<Node, Node> map) { Node popNode = stack.pop(); if (stack.isEmpty()) { map.put(popNode, null); } else { map.put(popNode, stack.peek()); } } /* * 先序遍历 */ public static void printPreOrder(Node head) { if (head == null) { return; } System.out.print(head.value + " "); printPreOrder(head.left); printPreOrder(head.right); } /* * 中序遍历 */ public static void printInOrder(Node head) { if (head == null) { return; } printPreOrder(head.left); System.out.print(head.value + " "); printPreOrder(head.right); } public static void main(String[] args) { int[] uniqueArr = { 3, 4, 5, 1, 2 }; Node head = getMaxTree(uniqueArr); printPreOrder(head); System.out.println(); printInOrder(head); } }题目：
给定一个整型矩阵map，其中只有0和1两种，求其中全是1的所有矩形区域中，最大的矩形区域为1的数量
例如：
1,1,1,0
其中，最大的矩形区域有3个1，所以返回3
两种解法：
public class MaximalRectangle { public static int maxRecSize(int[][] map) { if (map == null || map.length == 0 || map[0].length == 0) { return 0; } int maxArea = 0; int[] height = new int[map[0].length]; for (int i = 0; i < map.length; i++) { for (int j = 0; j < map[0].length; j++) { height[j] = map[i][j] == 0 ? 0 : height[j] + 1; } maxArea = Math.max(maxRecFromBottom(height), maxArea); } return maxArea; } public static int maxRecFromBottom(int[] height) { if (height == null || height.length == 0) { return 0; } int maxArea = 0; Stack<Integer> stack = new Stack<Integer>(); for (int i = 0; i < height.length; i++) { while (!stack.isEmpty() && height[i] <= height[stack.peek()]) { int j = stack.pop(); int k = stack.isEmpty() ? -1 : stack.peek(); int curArea = (i - k - 1) * height[j]; maxArea = Math.max(maxArea, curArea); } stack.push(i); } while (!stack.isEmpty()) { int j = stack.pop(); int k = stack.isEmpty() ? -1 : stack.peek(); int curArea = (height.length - k - 1) * height[j]; maxArea = Math.max(maxArea, curArea); } return maxArea; } public static void main(String[] args) { int[][] map = { { 1, 0, 1, 1 }, { 1, 1, 1, 1 }, { 1, 1, 1, 0 }, }; System.out.println(maxRecSize(map)); } } public class Exam { static int width,height; static int max=0; public static void dg(int sz[][],int x,int y,int w,int h) { int num_1=0; for(int i=0;i<w;i++) for(int j=0;j<h;j++) { if(sz[x+i][y+j]==1) { num_1++; } } if((w*h)==num_1) { if(num_1>max) { max=num_1; } if(w+1+x<=width) {dg(sz,x,y,w+1,h);} if(h+1+y<=height) {dg(sz,x,y,w,h+1);} } } public static void main(String args[]) { width=5; height=5; int shuzu[][]={{1,1,1,1,1} , {1,0,1,0,1} , {1,1,1,1,1} , {1,1,1,0,1} , {1,1,1,1,0} }; for(int i=0;i<width;i++) for(int j=0;j<height;j++) { dg(shuzu,i,j,1,1); } System.out.print(max); } }