算法进阶三

单调栈的应用

Image 14.png Image 15.png

单调栈的做法：找到每个数左边第一个比它大的数，右边第一个比它大的数串到它下面。

• 证明 ：形成的不是森林，而是一个颗数目。
  首先，数组中没有重复值。最大值一定会作为整棵树的头结点。任何一个节点都会找一个比他大的窜到他底下。所以，每一个节点都有归属，最终以最大值作为头部。因此，是一个树，不是多颗树，形不成森林。

• 证明：这个流程的正确性，不会形成多叉树，最多形成二叉树。
  因为我们的逻辑是：左边离我最近比我大的数，右边离我最近的比我大的数，挂在这两个数中较小的那个数的下面。会不会产生一个孩子有多个节点的时候。

Image 16.png

package com.znst;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Stack;

public class Demo2 {
    
    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> lBitmap = new HashMap<Node,Node>();
            HashMap<Node,Node> rBitmap = 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,lBitmap);
                }
                stack.push(curNode);
            }
            while(!stack.isEmpty()) {
                popStackSetMap(stack,lBitmap);
            }
            for(int i= nArr.length-1;i!=-1;i--) {
                Node curNode = nArr[i];
                while((!stack.isEmpty())&&stack.peek().value<curNode.value) {
                    popStackSetMap(stack,rBitmap);
                }
                stack.push(curNode);
            }
            while(!stack.isEmpty()) {
                popStackSetMap(stack,rBitmap);
            }
            Node head = null;
            for(int i=0;i!=nArr.length;i++) {
                Node curNode = nArr[i];
                Node left = lBitmap.get(curNode);
                Node right = rBitmap.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.println(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);
    }
}

求最大子矩阵大小

Image 17.png
Image 19.png

package com.znst;

import java.util.Stack;

public class Demo3 {

    public static 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;
    }
    //[4,3,2,5,6]
    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;
    }
}

案例：

Image 20.png
Image 1.png

证明：
思想：用小的去找大的，最小的找到第一大的就停，所以在最高和次高中间，从i出发，一定找到2个比他大的

Image 22.png
Image 2.png
Image 3.png
Image 4.png
Image 5.png
Image 6.png

package com.znst;

import java.util.Scanner;
import java.util.Stack;

public class Demo4 {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while(in.hasNextInt()) {
            int size = in.nextInt();
            int[] arr = new int[size];
            for(int i=0;i<size;i++) {
                arr[i]= in.nextInt();
            }
            System.out.println(communications(arr));
        }
        in.close();
    }
    public static int nextIndex(int size,int i) {//在一个环形数组中
        return i<(size -1)?(i+1):0;
    }
    public static long getInternalSum(int n) {//Ck2的实现
        return n==1L?0L:(long)n*(long)(n-1)/2L;//Ck2
    }
    public static class Pair{
        public int value;
        public int times;
        public Pair(int value) {
            this.value = value;
            this.times =1;
        }
    }
    
    public static long communications(int[] arr) {
        if(arr==null||arr.length<2) {
            return 0;
        }
        int size = arr.length;
        int maxIndex =0;
        for(int i=0;i<size;i++) {//找到最大值的位置
            maxIndex = arr[maxIndex]<arr[i]?i:maxIndex;
        }
        
        int value = arr[maxIndex];//最大值
        int index = nextIndex(size,maxIndex);//最大值位置的下一个
        long res =0L;
        Stack<Pair> stack = new Stack<Pair>();
        stack.push(new Pair(value));
        while(index!=maxIndex) {
            value = arr[index];
            while(!stack.isEmpty()&&stack.peek().value<value) {
                int times = stack.pop().times;
//              res+=getInternalSum(times)+times;  //C(2,times)+2*times;
//              res+=stack.isEmpty()?0:times;
                res+=getInternalSum(times)+2*times;
                
            }
            if(!stack.isEmpty()&&stack.peek().value==value) {
                stack.peek().times++;
            }else {
                stack.push(new Pair(value));
            } 
            index = nextIndex(size,index);
        }
        
        
        while(!stack.isEmpty()) { 
            int times = stack.pop().times;
            res+=getInternalSum(times);
            if(!stack.isEmpty()) {
                res+=times;
                if(stack.size()>1) {
                    res+=times;
                }else {
                    res+=stack.peek().times>1?times:0;
                }
            }
        }
        return res;
    }
    
}

Morris遍历：利用Morris遍历实现二叉树的先序，中序，后序遍历，时间复杂度O(N),额外空间复杂度O(1)。

来到的当前节点，记为Cur(引用)
1）如果cur无左孩子，cur向右移动(cur = cur.right)

2. 如果cur有左孩子，找到cur左子树上最右的节点，记为mostright
   a.如果mostright的right指针指向空，让其指向cur,cur向左移动（cur=cur.left）
   b.如果mostright指向cur,让其指向空，cur向右移动

   
   Image 7.png

Image 8.png

当cur来到4节点时，4的指针指向2，

Image 9.png
Image 10.png
Image 11.png

package com.znst;

import java.util.Scanner;
import java.util.Stack;

public class Demo4 {

    public static void main(String[] args) {
    
    }
    
    public static void process(Node head) {
        if(head == null) {
            return;
        }
        //1
        System.out.println(head.value);
        process(head.left);
        //2
        System.out.println(head.value);
        process(head.right);
        //3
        System.out.println(head.value);
    }
    
    public static class Node{
        public int value;
        Node left;
        Node right;
        public Node(int data) {
            this.value = data;
        }
    }

    public static void morrisIn(Node head) {
        if(head ==null) {
            return ;
        }
        Node cur = head;
        Node mostRight = null;
        while(cur!=null) {
            mostRight = cur.left;
            if(mostRight!=null) {//左孩子不为空
                while(mostRight.right!=null&&mostRight.right!=cur) {
                    mostRight = mostRight.right;
                }
                if(mostRight.right == null) {
                    mostRight.right = cur;
                    cur = cur.left;
                    continue;
                }else { 
                    mostRight.right = null;
                }
            }
            System.out.print(cur.value+" ");
            cur = cur.right;
        }
        System.out.println();
    }
    
    /*
     * morris改先序遍历
     */
    public static void morrisPre(Node head) {
        if(head==null) {
            return;
        }
        Node cur = head;
        Node mostRight = null;
        while(cur!=null) {
            mostRight = cur.left;
            if(mostRight!=null) {
                while(mostRight.right!=null&&mostRight.right!=cur) {
                    mostRight = mostRight.right;
                }
                if(mostRight.right ==null) {
                    mostRight.right = cur;
                    System.out.println(cur.value+" ");
                    cur = cur.left;
                    continue;
                }else {
                    mostRight.right = null;
                }
            }else {//当前节点没有左子树
                System.out.print(cur.value+" ");
            }
            cur = cur.right;
        }
        System.out.println();
    }
    
    public static void morrisPos(Node head) {
        if(head == null) {
            return ;
        }
        Node cur1 = head;
        Node cur2 = null;
        while(cur1!=null) {
            cur2 = cur1.left;
            if(cur2!=null) {
                while(cur2.right!=null&&cur2.right!=cur1) {
                    cur2 = cur2.right;
                }
                if(cur2.right ==null) {
                    cur2.right = cur1;
                    cur1 = cur1.left;
                    continue;
                }else {
                    cur2.right = null;
                    printEdge(cur1.left);
                }
            }
            cur1 = cur1.left;
        }
        printEdge(head); 
        System.out.println();
    }
    
    public static void printEdge(Node head) {
        Node tail = reverseEdge(head);
        Node cur = tail;
        while(cur != null) {
            System.out.print(cur.value+" ");
            cur = cur.right;
        }
        reverseEdge(tail);
    }
}

Image 12.png