单调栈结构是这样的，栈里放的内容要么是从小到大的，要么是从大到小的。
问题1：在一个数组中，每一个位置的num，找到左边离num近的>num的值，和右边离num近的>num的值。要求时间复杂度O(n)。
思路：构建一个栈底到栈顶，从大到小的栈。遍历数组，将数组中的元素num依次压栈，同时保证栈中的元素币num大，如果num大于栈中的元素，则将栈中的元素弹出，同时记录弹出的元素的结果。num就是弹出元素右边离他近的大于它的，栈中它挨着的元素就是左边离他近的大于它的元素。一直出栈，直到栈中元素大于将要入栈的元素，或者栈为空时停止。
当数组遍历完成后，栈中的元素依次弹出，此时它们弹出的元素的右边离它近的且大于它的元素为null，左边离它近的且大于它的元素为栈中下一个元素。
注意：当遇到两个相同的元素的时候，不弹出，将下标压在一起，弹出时一起弹出，同时更新它们左右比它们大的。
import java.util.ArrayList;
import java.util.Stack;
public class MonotonousStack {
public static class Num{
public int left;
public int right;
public int val;
public Num(int val){
this.val = val;
}
}
//这个node对象是为了处理重复的数的
public static class Node{
public int postion;
public int counter;
public Node(int postion){
this.counter = 1;
this.postion = postion;
}
}
public static ArrayList<Num> monotonousStack(int[] arrays){
if(arrays == null || arrays.length == 0) return null;
Stack<Node> stack = new Stack<>();
ArrayList<Num> res = new ArrayList<>();
for(int i = 0; i < arrays.length; i++){
while(!stack.isEmpty() && arrays[stack.peek().postion] < arrays[i]){
Node t = stack.pop();
//这些for循环是为了处理重复的数的，如果数组不重复，可以去掉
for(int j = 0; j < t.counter; j++){
Num num = new Num(arrays[t.postion]);
num.left = stack.isEmpty() ? -1 : arrays[stack.peek().postion];
num.right = arrays[i];
res.add(num);
}
}
if(!stack.isEmpty() && arrays[stack.peek().postion] == arrays[i])
stack.peek().counter++;
else
stack.push(new Node(i));
}
while(!stack.isEmpty()){
Node t = stack.pop();
//这些for循环是为了处理重复的数的，如果数组不重复，可以去掉
for(int j = 0; j < t.counter; j++){
Num num = new Num(arrays[t.postion]);
num.left = stack.isEmpty() ? -1 : arrays[stack.peek().postion];
num.right = -1;
res.add(num);
}
}
return res;
}
public static void main(String[] args){
int[] array = new int[]{5, 5, 4, 5 ,3, 6, 5, 3};
ArrayList<Num> arrayList = new MonotonousStack().monotonousStack(array);
for(Num num : arrayList){
System.out.println(num.val + " 左边：" + num.left + " 右边：" + num.right);
}
}
}
问题2：一个数组的MaxTree定义如下，数组中必须没有重复的元素。MaxTree是一棵二叉树，数组的每一个值对应一个二叉树节点。包括MaxTree树在内且其中的每一颗子树上，值最大的节点都是树的投。给定一个没有重复元素的数组arr，写出生成这个数组的MaxTree的函数，要求如果数组长度为N，时间复杂度O(N)，额外空间复杂度O(N)。
思路1：根据堆来做，大根堆的结构天然就是父节点大于等于左右子节点，时间复杂度O(N)。最好的解法
import java.util.Comparator;
import java.util.PriorityQueue;
public class MaxTree {
public static class Tree{
public Tree left;
public Tree right;
public int val;
public Tree(int val){
this.val = val;
}
}
public static Tree buildTree(int[] arr, int len, int pos){
if(arr == null || arr.length == 0)
return null;
if(pos >= len)
return null;
Tree head = new Tree(arr[pos]);
head.left = buildTree(arr, len, 2 * pos + 1);
head.right = buildTree(arr, len, 2 * pos + 2);
return head;
}
public static void printTree(Tree head){
if(head != null){
System.out.println(head.val);
printTree(head.left);
printTree(head.right);
}
}
public static void main(String[] args) {
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o2 - o1;
}
});
int[] array = new int[]{5, 9, 2, 1, 4, 3};
for(int i = 0; i < array.length; i++)
maxHeap.add(array[i]);
Object[] a = maxHeap.toArray();
for(int i = 0; i < a.length; i++){
array[i] = (int)a[i];
System.out.println(array[i]);
}
Tree tree = buildTree(array, array.length, 0);
printTree(tree);
}
}
思路二：数组中每一个数都能找到左边离它最大的和右边离它最大的数。如果一个数左右都为空，那么它是全局最大值，为头节点。如果一个数没左边只有右边或者没右边只有左边，那么它有唯一一个父节点，直接挂在它底下。如果一个数左右都有，那么选择较小的一个，挂在这个数的底下。
等过段时间再写把，累死
问题3：求最大子矩阵的大小。给定一个整形矩阵map，其中的值只有0和1两种，求其中全是1的所有矩形区域中， 最大的矩形区域为1的数量。
例如： 1 0 1 1
1 1 1 1
1 1 1 0
其中， 最大的矩形区域有6个1， 所以返回6。
将其放到一个矩阵中，同时从第0行开始计算，以该行打底时，直方图的最大面积。
如，第0行，数组为[1, 0, 1, 1]，此时可以求直方图的最大面积
然后以第一行打底，此时数组为[2, 1, 2, 2]，同理求直方图的最大面积。
然后以第2行打底，此时数组为[3, 2, 3, 0]。
类似的题目：给定一个数组，表示的是每个位置的直方图的高度，求直方图中连续部分的最大面积
利用单调栈，构成一个有栈底到栈顶是从小到大的结构，当要入栈的元素num小于栈顶元素时，栈顶元素出栈，同时对该元素左右能到达的边界进行记录，这样以这个元素为中心的面积就可以求出来了。
等过段时间再写把，累死
