问题描述: n个不相同元素顺序输入到 一个栈, 栈可以里的元素可在任意时刻出栈. 求出栈的可能序列数. 
 

 
 
这是一个填空题, 求出当N等于5的情况的可能序列数. 很容易可以得到N等于2,3,4 时的序列数为 2,5,14. 这可通过在已有序列的基础上添加下一元素的可能性来寻找规律. 
 
当N为2时, 序列为 2,1 及 1,2. 当N为3时, 3可从2的序列中的最后插入, 第二个位置插入. 以及出现在2,1的前面. 如下图:
 

 
 

 
 
由此可得 当N为3时, 可能插入的位置为5, 即出栈序列的可能数 为 5. 再来看看当n为4时:
 

 
 

 
 
一共有14个位置可以插入. 共同的地方是最前只能插入一个, 最后及倒数第二个位置全都可以进行插入. 以及倒序输出的那个行的任意位置都可以进入插入. 此时, 输出的可能序列增加到了 14个. 那么当n为5 时, 可能输出的序列是多少个呢? 好吧, 我没找出规律来, 求解答. 
 
 
当然, 这个问题可以解决, 那就依靠我们强大的计算机吧. 
 
ruby代码如下:
 
 
a = [] #用来存放输出到栈中的数的
for i in 1 .. ARGV[0].to_i 
	a[i-1] = i
end
stack = []
printarray = [] #栈中输出先放至这个数组中, 满了就存放到vav中
vav = Array.new(){[]} #此也就是数组的数组, 存放合法的输出序列

def find(ith, stack, printarray, a, stack_push, vav)
	stack = Array.new stack
	printarray = Array.new printarray
	if ith == ARGV[0].to_i #若顺序输出完毕, 则栈中全部出栈, 存入打印数组中
		while !stack.empty?
			printarray.push stack.pop
		end
		vav.push printarray
	else
		if stack_push 
			stack.push a[ith]
			find(ith+1, stack, printarray, a, true, vav)
			find(ith+1, stack, printarray, a, false, vav)
		elsif !stack.empty?
			printarray.push stack.pop
			find(ith, stack, printarray, a, true, vav)
			find(ith, stack, printarray, a, false, vav)
		end
	end
end

find(0, stack, printarray, a, true, vav)
vav.uniq! #除去vav中的重复序列
vav.each{|i|
	p i
}
p vav.size
 
 

 
 
现在让我们来看来结果是什么, 首先先试一下  n 为3, 及 n 为 4 时. 如下:
 
 

 
 
结果是正确的, n 为5,6,7 时结果分别为: 42 , 132, 429.
 
 
 
详细的看一下wiki百科: 卡塔兰数
 

 

问题
 
队列中有从1到7（由小到大排列）的7个整数，问经过一个整数栈后，出栈的所有排列数有多少？
如果整数栈的容量是4（栈最多能容纳4个整数），那么出栈的排列数又是多少？
 
问题1代码
 

public class Catalan {

    public static int answers = 0;
    int maxStackSize = 4; //栈最大容量

    public static void go(int deq, int sta) {
        if(deq>0) {
            go(deq-1, sta+1);
        }
        if(sta>0) {
            go(deq, sta-1);
        }
        if(deq==0&&sta==0) {
            answers++;
        }
    }

    public static void main(String[] args) {
        Deque from = new Deque();
        Deque to = new Deque();
        Stack s = new Stack();
        for(int i=1;i<=7;i++) {
            from.addLast(i);
        }
        go(7, 0);
        System.out.println(answers);
    }
}
 
问题2代码
 

public class Catalan {

    public static int answers = 0;
    int maxStackSize = 4;

    public static void go(int deq, int sta) {
        if(deq>0 &&sta<maxStackSize) {  //仅此行比问题1多了一个限制
            go(deq-1, sta+1);
        }
        if(sta>0) {
            go(deq, sta-1);
        }
        if(deq==0&&sta==0) {
            answers++;
        }
    }

    public static void main(String[] args) {
        Deque from = new Deque();
        Deque to = new Deque();
        Stack s = new Stack();
        for(int i=1;i<=7;i++) {
            from.addLast(i);
        }
        go(7, 0);
        System.out.println(answers);
    }
}

import java.math.BigInteger;

/**
问题描述：
	n个元素的出栈次序
	f(n)=f(0)*f(n-1)+f(1)*f(n-2)...+f(n-2)*f(1)+f(n-1)*f(0)
输出样例：
0:1
1:1
2:2
3:5
4:14
5:42
6:132
7:429
8:1430
9:4862
10:16796
11:58786
12:208012
13:742900
14:2674440
15:9694845
16:35357670
17:129644790
18:477638700
19:1767263190
20:6564120420

 * @author Vivinia
 */
public class StackNum {
	static BigInteger[] num=new BigInteger[101];         //使用数组存储之前计算过的数据
	public static void main(String[] args) {
		for(int i=0;i<=100;i++)         
			num[i]=BigInteger.valueOf(0);           //先全部赋值为0
		num[0]=BigInteger.valueOf(1);             
		for(int i=0;i<=100;i++)
			System.out.println(i+":"+f(i));
	}

	private static BigInteger f(int n) {
		BigInteger total=BigInteger.valueOf(0);
		if(n==0)
			return num[0];        //0是退出递归的边界条件
		if(num[n]!=BigInteger.valueOf(0))
			return num[n];        //判断以前是否计算过数据，如果计算过数据直接从数组中取出，不用再次计算
		for(int i=0;i<n;i++)
			total=total.add((f(i).multiply(f(n-i-1))));   //循环累加每次成绩
		num[n]=total;        //将该次数据存储起来
		return total;
	}

}
 

 
 
需要注意的地方：
 
1.首先找到通用公式 f(n)=f(0)*f(n-1)+f(1)*f(n-2)...+f(n-2)*f(1)+f(n-1)*f(0)，嗯，我从网上查的。。。
 
2.核心代码就是递归中的for循环语句，外加退出递归的return 1，但是如果只这样递归，在n为16时就明显感觉时间变慢，大约接近一秒钟，然后往后时间为指数增长，到20就已经超过人的耐心等待时间了，这是因为每次计算一个数，都把前边的数据重新算了一遍，做了很多无用功，所以定义一个数组把每次计算的数据存储起来，以后先查询数组，数组没有存储再计算；
 
3.虽然网上搜着long型数据很大，但是如果用long到n=20时就溢出了，所以改用BigInteger型，现在测试到100输出都没问题，而且时间很快，只不过就是不知道数据的数据对不对，反正很大。。。

通过使用栈这个简单的结构，我们可以巧妙地降低一些问题的时间复杂度。
 
单调栈性质：
 
1、若是单调递增栈，则从栈顶到栈底的元素是严格递增的。若是单调递减栈，则从栈顶到栈底的元素是严格递减的。
 
2、越靠近栈顶的元素越后进栈。（显而易见）
 
本文介绍单调栈用法
 
通过一道题来说明。
 
POJ2559
 
1. 题目大意：链接
 
给出一个柱形统计图(histogram), 它的每个项目的宽度是1， 高度和具体问题有关。 现在编程求出在这个柱形图中的最大面积的长方形。
 
7 2 1 4 5 1 3 3
 
7表示柱形图有7个数据，分别是 2 1 4 5 1 3 3， 对应的柱形图如下，最后求出来的面积最大的图如右图所示。
 
 
做法1：枚举每个起点和终点，矩形面积就是长*最小高度。O(N^3)
 
做法2：区间最小值优化。O(N^2)
 
做法3：以每一个下标为中心向两边扩，遇到更短的就停，这样我们可以确定以每一个下标高度为最高的矩形。O(N^2)
 
单调栈：维护一个单调递增栈，所有元素各进栈和出栈一次即可。每个元素出栈的时候更新最大的矩形面积。
 
过程：
 
1）判断当前元素小于栈顶
 
2）条件满足，就可以更新栈顶元素的最大长度了，并且把栈顶弹出
 
3）继续执行（1），直到条件不满足。
 
 
 
重要结论：
 
1）栈顶下面一个元素一定是，栈顶左边第一个比栈顶小的元素
 
2）当前元素一定是，右边第一个比栈顶小的元素。
 
为什么呢？
 
比如这是个栈
 
，
 
1）如果右边存在距离更近的比1号小的数，1号早已经弹出了。
 
2）如果左边有距离更近的比1号小的数，
 
                如果它比2号小，它会把2号弹出，自己成为2号
 
                 如果它比2号大，它不会弹出2号，但是它会压栈，变成2号，原来的2号成为3号。
 
所以不管怎么说，这个逻辑是正确的。
 
最后放代码并讲解
 
 
 
下面看一道难一些的题
 
LeetCode 85 Maximal Rectangle
 
1 0 1 0 0
 
1 0 1 1 1
 
1 1 1 1 1
 
1 0 0 1 0
 
Return 6.二三行后面那六个1
 
 
 
给定一个由二进制组成的矩阵map，找到仅仅包含1的最大矩形，并返回其面积。
 
这道题是一行一行的做。对每一行都求出每个元素对应的高度，这个高度就是对应的连续1的长度，然后对每一行都更新一次最大矩形面积。
 
连续1长度也很好更新，本个元素是0，长度就是0，本个元素是1，那就加上之前的。
 
具体思路代码中讲解。
 
import java.util.Stack;

public class MaximalRectangle {

	public static int 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;//0长度为0，1长度为前面+1
			}
			maxArea = Math.max(maxRecFromBottom(height), maxArea);//调用第一题的思想
		}
		return maxArea;
	}

	//第一题思路
	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;
	}

	public static void main(String[] args) {
		int[][] map = { { 1, 0, 1, 1 }, { 1, 1, 1, 1 }, { 1, 1, 1, 0 }, };
		System.out.println(maxRecSize(map));
	}

}