美文网首页
算法进阶三

算法进阶三

作者: fly152 | 来源:发表于2018-09-04 16:38 被阅读0次

    单调栈的应用

    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)

    1. 如果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

    相关文章

      网友评论

          本文标题:算法进阶三

          本文链接:https://www.haomeiwen.com/subject/yvqgwftx.html