单调栈的应用
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)
-
如果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
