單調棧

單調棧結構是這樣的，棧裡放的内容要麼是從小到大的，要麼是從大到小的。

問題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

将其放到一個矩陣中，同時從第0行開始計算，以該行打底時，直方圖的最大面積。

如，第0行，數組為[1, 0, 1, 1]，此時可以求直方圖的最大面積

然後以第一行打底，此時數組為[2, 1, 2, 2]，同理求直方圖的最大面積。

然後以第2行打底，此時數組為[3, 2, 3, 0]。

類似的題目：給定一個數組，表示的是每個位置的直方圖的高度，求直方圖中連續部分的最大面積

利用單調棧，構成一個有棧底到棧頂是從小到大的結構，當要入棧的元素num小于棧頂元素時，棧頂元素出棧，同時對該元素左右能到達的邊界進行記錄，這樣以這個元素為中心的面積就可以求出來了。

等過段時間再寫把，累死