单调栈

单调栈结构是这样的，栈里放的内容要么是从小到大的，要么是从大到小的。

问题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。

思路.png

类似的题目：给定一个数组，表示的是每个位置的直方图的高度，求直方图中连续部分的最大面积
利用单调栈，构成一个有栈底到栈顶是从小到大的结构，当要入栈的元素num小于栈顶元素时，栈顶元素出栈，同时对该元素左右能到达的边界进行记录，这样以这个元素为中心的面积就可以求出来了。

等过段时间再写把，累死