栈相关内容

基础知识

	栈的最大特点是先进后出（后入先出），为了保证后入先出的顺序，栈的插入和删除操作都发生在栈顶。栈的操作可以用日常生活中洗碗来理解，先洗的
碗总是放在最下面，使用的时候是从最上面取。

常用函数

序号	函数	函数功能
1	push(e)	元素入栈
2	pop	位于栈顶的元素出栈，并返回元素
3	peek	返回位于栈顶的元素，该元素不出栈

例题解答

1、后缀表达式

题目

	后缀表达式是一种算术表达式，它的操作符在操作数的后面。输入一个用字符串数组表示的后缀表达式，请输出该后缀表达式的计算结果，假设输入的一
定是有效的后缀表达式。例如，后缀表达式["2","1","3","*","+"]对应的算术表达式是"2 + 1 * 3"，因此输出它的计算结果5。

分析

	后缀表达式又叫逆波兰式（Reverse Polish Notation，RPN），是一种将操作符放在操作数后面的算术表达式。通常使用的时中缀表达式，即操作符
在两个操作数中间。使用后缀表达式的好处是不需要使用括号。根据题目分析可使用栈的数据结构来解决，符合后入先出的特性,遍历数组时，遇到数字时入
栈，遇到符号时，从栈中取出两个数字利用符号进行计算并再将结果入栈。

示例代码

public int evalRPN(String[] tokens){Stack<Integer> stack = new Stack<>();for(String token : tokens){switch(token){case "+":case "-":case "*":case "/":int num1 = stack.pop();int num2 = stack.pop();//需要注意传值顺序和方法对应上，因为减法和除法会有区别stack.push(calculate(num2,num1,token));break;default:stack.push(Integer.parseInt(token));}}return stack.pop();
}
private int calculate(int num2, int num1, String token){switch(token){case "+":return num2+ num1;case "-":return num2 - num1;case "*":return num2 * num1;case "/":return num2 / num1;default:return 0;}
}

2、小行星碰撞

题目

	输入一个表示小行星的数组，数组中每个数字的绝对值表示小行星的大小，数字的正负号表示小行星运动的方向，正号表示向右飞行，负号表示向左飞行。
如果两颗小行星相撞，那么体积小的小行星将会爆炸最终消失，体积较大的小行星不受影响。如果相撞的两颗小行星大小相同，那么它们都会爆炸消失。飞行
方向相同的小行星永远不会相撞。求最终剩下的小行星。例如，有6颗小行星[4,5,-6,4,8,-5]，它们相撞之后最终剩下3颗小行星[-6,4,8]。

分析

	如果一颗小行星向右飞行，那么可以将它入栈，如果一颗小行星向左飞行的，那么位于栈顶的小行星向右飞行，那么一定相撞，如果位于栈顶的小行星
较小，那么它将爆炸消失，将其出栈，然后判断它是否与下一颗栈顶的小行星碰撞。如果小行星与栈中所有小行星相撞之后仍然没有爆炸消失，那么将它入栈。

示例代码

public int[] asteroidConllision(int[] asteroids){Stack<Integer> stack = new Stack<>();for(int as : asteroids){//当栈不为空并且栈顶数据大于0，且栈顶数据小于当前数据时，将栈顶出栈，栈顶数据爆炸while(!stack.isEmpty() && stack.peek() > 0 && stack.peek() < -as){stack.pop();}//当栈不为空，并且当前数据是负数，并且栈顶数据和当前数据是相反数，则将数据出栈，并且当前数据不入栈，两个都爆炸if(!stack.empty() && as < 0 && stack.peek() == -as){stack.pop();}else if(as > 0 ||stack.isEmpty() || stack.peek() < 0){stack.push(as);}}return stack.stream().mapToInt(i -> i).toArray();
}

3、每日温度

题目

	输入一个数组，它的每个数字时某天的温度。请计算每天需要等几天才会出现更高的温度。例如，如果输入数组[35,31,33,36,34]，那么输出
[3,1,1,0,0]。由于第一天的温度是35℃，要等3天才会出现更高的温度36℃，因此对应的输出为3。第四天的温度是36℃，后面没有更高的温度，它对应的
输出是0。其它依次类推。

分析

	解法一：直接使用两个循环扫描可以解决该问题，嵌套循环可以知道当前数子后面第几个比它大。解法二：使用栈保存每天的温度在数组中的下标，每次从数组中读取一个温度，然后将其与栈中保存的温度（根据下标得到的温度）进行比较，如果当前
温度比位于栈顶的温度高，那么就能知道位于栈顶那一天需要等待几天才会出现更高的温度，然后出栈1次，将当前温度与下一个位于栈顶的温度进行比较。
如果栈中已经没有比当前温度低的温度，则将当前温度在数组中的下标入栈。

示例代码

public int[] dailyTemperatures(int[] temperatures){int length = temperatures.length;int[] result = new int[length];Stack<Integer> stack = new Stack<>();for(int i = 0; i < length; i ++){while(!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]){int prev = stack.pop();result[prev] = i - prev;}stack.push(i);}return result;
}

4、直方图最大矩形面积

题目

	直方图是由排列在同一基线上的相邻柱子组成的图形。输入一个由非负数组成的数组，数组中的数字是直方图中柱子的高。求直方图中最大矩形面积。假
设直方图中柱子的宽都是1.例如，输入数组[3,2,5,4,6,1,4,2]，该直方图面积是12，由[5,4,6]三个中最小的4，决定的面积。

分析

	矩形的面积等于宽乘以高，因此只要能确定每个矩形的宽和高，就能计算它的面积。如果直方图中一个矩形从下标为i的柱子开始，到下标为j的柱子结束，
那么这两根柱子之间的矩形（含两端的柱子）的宽是j - i + 1。矩形的高就是两根柱子时间的所有柱子最矮的高度。

示例代码

//解法一： 蛮力法
public int largestRectangleArea(int[] heights){int maxArea = 0;for(int i = 0; i < heights.length; i ++){int min = heights[i];for(int j = i; j < heights.length; j ++){min = Math.min(min,heights[j]);int area = min * (j - i + 1);maxArea = Math.max(area,maxArea);}}return maxArea;
}
// 分治法
public int largestRectangleArea(int[] heights){return helper(heights,0,heights.length);
}
private int helper(int[] heights, int start, int end){if(start == end){return 0;}if(start + 1 == end){return heights[start];}//先求出最小下标int minIndex = start;for(int i = start + 1; i < end; i ++){if(heights[i] < heights[minIndex]){minIndex = i;}}//求出面积int area = (end - start) * heights[minIndex];//求出最小矩形左边面积int left = helper(heights,start,minIndex);//求出最小矩形右边面积int right = helper(heights,minIndex + 1,end);//比较最大的面积然后返回area = Math.max(area,left);return Math.max(area,right);
}
//单调栈法
public int largestRectangleArea(int[] heights){//栈中存放数组下标Stack<Integer> stack = new Stack<>();stack.push(-1);int areaMax = 0;for(int i = 0; i < heights.length; i ++){//如果当前高度比栈顶对应的高度低，则计算当前到栈顶下标之间的面积，并判断得到最大面积while(stack.peek() != -1 && heights[stack.peek()] >= heights[i]){int height = heights[stack.pop()];int width = i - stack.peek() - 1;areaMax = Math.max(areaMax,height * width);}stack.push(i);}//如果栈中还有元素，说明栈中的是依次递减高度的下标，得到其最大面积while(stack.peek() != -1){int height = heights[stack.pop()];int width = heights.length - stack.peek() - 1;areaMax = Math.max(areaMax,height * width);}return areaMax;
}

5、矩阵中的最大矩形

题目

	请在一个由0、1组成的矩阵中找出最大的只包含1的矩阵并输出它的面积。

分析

	分析可以将矩阵看出多个直方图来计算面积，每一行以及这一行上面的所有行数据相加看作一个直方图，然后就可以比较每个直方图矩形的最大面积，直
方图最大面积即为矩阵的最大矩形。

示例代码

public int maximalRectanle(char[][] matrix){if(matrix == null || matrix.length == 0 || matrix[0].length == 0){return 0;}int[] heights = new int[matrix[0].length];int maxArea = 0;for(char[] row : matrix){for(int i = 0; i < row.length; i ++){if(row[i] == '0'){heights[i] = 0;}else{heights[i] ++;}}maxArea = Math.max(maxArea,largestRectangleArea(heights));}return maxArea;
}public int largestRectangleArea(int[] heights){Stack<Integer> stack = new Stack<>();stack.push(-1);int maxArea = 0;for(int i = 0; i < heights.length;i ++){while (stack.peek() != -1 && heights[stack.peek()] >= heights[i]){int height = heights[stack.pop()];int width = i - stack.peek() - 1;maxArea = Math.max(maxArea,height * width);}stack.push(i);}while (stack.peek() != -1){int height = heights[stack.pop()];int width = heights.length - stack.peek() - 1;maxArea = Math.max(maxArea,height * width);}return maxArea;}

总结

	栈的插入、删除操作都发生在栈的顶部，在栈中插入、删除数据的顺序为“后入先出”，即最后添加的数据最先被删除。Java中类型Stack实现了该功能。