经典结构单调栈结构-白红宇

经典结构单调栈结构

阅读量：6368 次

发布时间：2019-06-23

本文共 8320 字，大约阅读时间需要 27 分钟。

内容：

1、原始问题

2、拓展题

1、原始问题

题目描述：

给你一个数组，找出数组中每个数左边离它近的比它大的数和右边离它近的比它大的数要求算法时间复杂度为O(N)

解题思路：

使用一个栈，要求每次元素进栈后要维持栈中从栈底到栈顶元素值是从大到小排列的约定。将数组中的元素依次进栈，

如果某次元素进栈后会违反了上述的约定（即该进栈元素比栈顶元素大），就先弹出栈顶元素，并记录该栈顶元素的信息：

该元素左边离它近的比它大的是该元素出栈后的栈顶元素，如果出栈后栈空，那么该元素左边没有比它大的数

该元素右边离它近的比它大的是进栈元素

然后再尝试将进栈元素进栈，如果进栈后还会违反约定那就重复操作“弹出栈顶元素并记录该元素信息”，直到符合约定

或栈中元素全部弹出时再将该进栈元素进栈。当数组所有元素都进栈之后，栈势必不为空，弹出栈顶元素并记录信息：

该元素右边没有比它大的数

该元素左边离它近的比它大的数是该元素从栈弹出后的栈顶元素，如果该元素弹出后栈为空，那么该元素左边没有比它大的数

由于每个元素仅进栈一次、出栈一次，且出栈时能得到题目所求信息，因此时间复杂度为 O(N)

代码：

1 public class FindLeftAndRightBigger { 2     // 记录每个数左边离它近的比它大的数和右边离它近的比它大的数的表 3     public static HashMap
     
       lBigMap = new HashMap
      
       (); 4     public static HashMap
       
         rBigMap = new HashMap
        
         (); 5  6     private static void popStackSetLMap(Stack
         
           stack, 7             HashMap
          
            map) { 8 // 弹出栈中元素并记录最大信息(左边最大信息) 9 int popElement = stack.pop();10 if (stack.isEmpty()) {11 map.put(popElement, null);12 } else {13 map.put(popElement, stack.peek());14 }15 }16 17 public static void findLeftAndRightBigger(int[] arr) {18 // 单调栈主逻辑19 Stack
           
             stack = new Stack
            
             ();20 for (int i = 0; i < arr.length; i++) {21 // 遍历所有元素入栈 不符合入栈条件 弹出并记录信息22 while (!stack.isEmpty() && arr[stack.peek()] < arr[i]) {23 int top = stack.peek();24 popStackSetLMap(stack, lBigMap); // 左边最大25 rBigMap.put(top, i); // 右边最大26 }27 stack.push(i);28 }29 while (!stack.isEmpty()) {30 // 所有元素已经入栈过 依次出栈并记录信息31 int top = stack.peek();32 popStackSetLMap(stack, lBigMap); // 左边最大33 rBigMap.put(top, null); // 右边最大34 }35 }36 37 public static void printRes() {38 // 输出结果39 for (Entry
             
               entry : lBigMap.entrySet()) {40 System.out.println("element: " + entry.getKey() + " - leftBigger:"41 + entry.getValue());42 }43 for (Entry
              
                entry : rBigMap.entrySet()) {44 System.out.println("element: " + entry.getKey() + " - rightBigger:"45 + entry.getValue());46 }47 }48 49 // test50 public static void main(String[] args) {51 int[] arr = { 3, 4, 5, 1, 2 };52 findLeftAndRightBigger(arr);53 printRes();54 }55 }

2、拓展题

(1)构造数组的MaxTree

题目描述：

给定一个没有重复元素的数组A，定义A上的MaxTree如下：

MaxTree的根节点为A中最大的数，根节点的左子树为数组中最大数左边部分的MaxTree，

右子树为数组中最大数右边部分的MaxTree。请根据给定的数组A，设计一个算法构造这个数组的MaxTree

思路：

一种思路是用堆做，把数组建成一个大根堆即可(O(N))

另外一种是用单调栈去做，使用一个栈底到栈顶单调递减的单调栈，将这些数 arr[] 依次入栈，

记录每个数左边离它近的比它大的数，保存在 left[] 中（下标和 arr[] 一一对应），

记录每个数右边离它近的比它大的数，保存在 right[] 中

遍历 arr[] 建树：

left[i] 和 right[i] 都不存在的，说明 arr[i] 是大的数，将其作为根节点；

left[i] 和 right[i] 都存在则将arr[i]作为其中最小值节点的孩子节点，

只有一个存在（如 left[i] ）那就将 arr[i] 作为 left[i] 的孩子节点

这样建出的树必然是一颗二叉树，证明省略

代码：

1 public class MaxTree {  2     public static class Node {  3         public int value;  4         public Node left;  5         public Node right;  6   7         public Node(int data) {  8             this.value = data;  9         } 10     } 11  12     private static void popStackSetMap(Stack
     
       stack, 13             HashMap
      
        map) { 14         // 弹出栈中元素并记录最大信息 15         Node popNode = stack.pop(); 16         if (stack.isEmpty()) { 17             map.put(popNode, null); 18         } else { 19             map.put(popNode, stack.peek()); 20         } 21     } 22      23     private static void guaNode(Node child, Node parent){ 24         // 将child节点挂在parent节点下 25         if (parent.left == null) { 26             parent.left = child; 27         } else { 28             parent.right = child; 29         } 30     } 31  32     public static Node getMaxTree(int[] arr) { 33         // 初始化node 34         Node[] nArr = new Node[arr.length]; 35         for (int i = 0; i < arr.length; i++) { 36             nArr[i] = new Node(arr[i]); 37         } 38         // 记录信息的结构 39         Stack
       
         stack = new Stack
        
         (); 40         HashMap
         
           lBigMap = new HashMap
          
           (); 41 HashMap
           
             rBigMap = new HashMap
            
             (); 42 // 单调栈结构(生成左最大和右最大) 43 for (int i = 0; i < arr.length; i++) { 44 Node cur = nArr[i]; 45 while (!stack.isEmpty() && stack.peek().value < cur.value) { 46 popStackSetMap(stack, lBigMap); 47 } 48 // 节点入栈 49 stack.push(cur); 50 } 51 while (!stack.isEmpty()) { 52 popStackSetMap(stack, lBigMap); 53 } 54 for (int i = nArr.length - 1; i >= 0; i--) { 55 Node cur = nArr[i]; 56 while (!stack.isEmpty() && stack.peek().value < cur.value) { 57 popStackSetMap(stack, rBigMap); 58 } 59 // 节点入栈 60 stack.push(cur); 61 } 62 while (!stack.isEmpty()) { 63 popStackSetMap(stack, rBigMap); 64 } 65 // 遍历节点根据生成的左最大值表和右最大值表建树 66 Node head = null; 67 for (int i = 0; i < nArr.length; i++) { 68 Node cur = nArr[i]; 69 Node left = lBigMap.get(cur); 70 Node right = rBigMap.get(cur); 71 if (left == null && right == null) { 72 head = cur; 73 } else if (left == null) { 74 // 将cur挂在right下 75 guaNode(cur, right); 76 } else if (right == null) { 77 // 将cur挂在left下 78 guaNode(cur, left); 79 } else { 80 // 将cur挂在两端较小的节点上 81 Node parent = left.value < right.value ? left : right; 82 guaNode(cur, parent); 83 } 84 } 85 86 return head; 87 } 88 89 // 打印二叉树的入口函数 90 public static void printTree(Node head) { 91 System.out.println("Binary Tree:"); 92 printInOrder(head, 0, "H", 17); 93 System.out.println(); 94 } 95 96 // 为节点加上左右两边的空格 97 public static String getSpace(int num) { 98 String space = " "; 99 StringBuffer buf = new StringBuffer("");100 for (int i = 0; i < num; i++) {101 buf.append(space);102 }103 return buf.toString();104 }105 106 // 打印二叉树的主逻辑函数 107 public static void printInOrder(Node head, int height, String to, int len) {108 /*109 * head 头节点110 * height 当前高度111 * to 代表是左子树还是右子树 => 为H时代表根节点112 * len 代表每个节点最多占的宽度113 * */114 if (head == null) {115 return;116 }117 118 // 继续打印右子树119 printInOrder(head.right, height + 1, "v", len);120 121 String val = to + head.value + to;122 int lenM = val.length(); // 节点(加上节点标志)的长度123 int lenL = (len - lenM) / 2; // 节点左边的长度124 int lenR = len - lenM - lenL; // 节点右边的长度125 val = getSpace(lenL) + val + getSpace(lenR); // 为节点加上左右两边的空格126 System.out.println(getSpace(height * len) + val); // 打印当前节点127 128 // 继续打印左子树129 printInOrder(head.left, height + 1, "^", len);130 }131 132 public static void main(String[] args) {133 int[] arr = { 3, 4, 5, 1, 2 };134 Node head = getMaxTree(arr);135 printTree(head);136 }137 138 }

(2)求最大子矩阵的大小

题目描述：

给定一个整型矩阵 map，其中的值只有 0 和 1 两种，求其中全是1的所有矩形区域中，最大的矩形区域为1的数量。

例如：

1　　1　　1　　0

其中，最大的矩形区域有 3 个 1，所以返回3。

再如：

1　　0　　1　　1

1　　1　　1　　1

1　　1　　1　　0

其中，最大的矩形区域有 6 个 1，所以返回6。

代码：

1 public class MaximalRectangle { 2     // 将矩阵问题转换成数组求直方图最大面积问题求解 3     public static int maxRecSize(int[][] map) { 4         if (map == null || map.length == 0 || map[0].length == 0) { 5             return 0; 6         } 7         int maxArea = 0; 8         // TODO - 核心代码如下: 9         int[] height = new int[map[0].length];10         for (int i = 0; i < map.length; i++) {11             for (int j = 0; j < map[0].length; j++) {12                 // 计算每一行中的值(上一个位置为0值为0否则值+1)13                 height[j] = map[i][j] == 0 ? 0 : height[j] + 1;14             }15             maxArea = Math.max(maxRecFromBottom(height), maxArea);16         }17 18         return maxArea;19     }20 21     // height =》 [4, 3, 2, 5, 6] =》 直方图22     public static int maxRecFromBottom(int[] height) {23         // 计算直方图中最大的矩阵面积24         if (height == null || height.length == 0) {25             return 0;26         }27         int maxArea = 0;28         // TODO - 核心代码如下:29         Stack
     
       stack = new Stack
      
       ();30         // 遍历入栈 出栈时扩范围31         for (int i = 0; i < height.length; i++) {32             while (!stack.isEmpty() && height[i] <= height[stack.peek()]) {33                 // 此时i是右边界 k是左边界34                 int j = stack.pop();35                 int k = stack.isEmpty() ? -1 : stack.peek();36                 int curArea = (i - k - 1) * height[j]; // 某个可以扩的最大范围大小37                 maxArea = Math.max(maxArea, curArea);38             }39             stack.push(i);40         }41         // 都入栈了之后 遍历出栈并扩范围42         while (!stack.isEmpty()) {43             // 此时height.length是右边界(数组最右边) k是左边界44             int j = stack.pop();45             int k = stack.isEmpty() ? -1 : stack.peek();46             int curArea = (height.length - k - 1) * height[j];47             maxArea = Math.max(maxArea, curArea);48         }49         return maxArea;50     }51 52 }

转载于:https://www.cnblogs.com/wyb666/p/10284522.html

你可能感兴趣的文章