1.栈（一）

题目汇总：https://leetcode-cn.com/tag/stack/

20. 有效的括号简单

42. 接雨水困难[✔]

71. 简化路径中等

84. 柱状图中最大的矩形困难※※※

85. 最大矩形困难※※※

94. 二叉树的中序遍历中等[✔]

103. 二叉树的锯齿形层次遍历中等[✔]

144. 二叉树的前序遍历中等

145. 二叉树的后序遍历困难

150. 逆波兰表达式求值中等[✔]

20. 有效的括号简单

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。
   注意空字符串可被认为是有效字符串。
   示例 1:
   输入: "()"
   输出: true
   示例 2:
   输入: "()[]{}"
   输出: true
   示例 3:
   输入: "(]"
   输出: false

思路：栈

class Solution {//执行用时：2 ms, 在所有 Java 提交中击败了81.59%的用户
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<Character>();
        for(int i=0;i<s.length();i++){
            char c = s.charAt(i);
            if(c=='(' || c=='{' || c=='['){
                stack.push(c);//遇到左括号就入栈
            }
            else{
                if(stack.isEmpty()){
                    return false;
                }    
                char popChar = stack.pop();
                if((c==')'&&popChar!='(')||(c=='}'&&popChar!='{')||(c==']'&&popChar!='['))
                    return false;
                
             }
        }
        return stack.isEmpty();
    }
}

class Solution {//执行用时：1 ms, 在所有 Java 提交中击败了98.76%的用户
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<Character>();
        for(char c:s.toCharArray()){
            if(c == '(')    stack.push(')');
            else if(c == '[')   stack.push(']');
            else if(c == '{')   stack.push('}');
            else if(stack.isEmpty() || c != stack.pop())    return false;
        }
    return stack.isEmpty();
    }
}

42. 接雨水困难

精选题解的几种解法都超级棒
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
输入: [0,1,0,2,1,0,1,3,2,1,2,1]，输出: 6

思路一：暴力法，时间复杂度O(n*n)

对于数组中的每个元素，下雨后水能达到的最高位置，等于两边最大高度的较小值减去当前高度的值。为了找到最大值每次都要向左和向右扫描一次。

class Solution {
    public int trap(int[] height) {
        int sum = 0;
        for(int i=1;i<height.length-1;i++){
            int max_left = 0;
            int max_right = 0;
            //左边最高列
            for(int j=i;j>=0;j--){
                if(height[j]>max_left)
                    max_left = height[j];
            }
            //右边最高列
            for(int j=i;j<height.length;j++){
                if(height[j]>max_right)
                    max_right = height[j];

            }
            int min = Math.min(max_left,max_right);
            //只有较小的一列大于当前列的高度才会有水
            if (min > height[i]) 
                sum += (min - height[i]);
        }
    return sum;
    }
}

思路二：动态规划，时间复杂度O(n)

在按列求解的暴力法中，对于每一列，我们求它左边最高的墙和右边最高的墙，都是重新遍历一遍所有高度。为了降低时间复杂度，定义两个数组，max_left [i] 代表第 i 列左边最高的墙的高度，max_right[i] 代表第 i 列右边最高的墙的高度。

class Solution {
    public int trap(int[] height) {
        int sum = 0;
        int[] max_left = new int[height.length];
        int[] max_right = new int[height.length];
        for(int i = 1; i < height.length - 1; i++){
            max_left[i] = Math.max(max_left[i-1],height[i-1]);
        }
        for(int  i = height.length - 2; i >= 0; i--){
            max_right[i] = Math.max(max_right[i + 1], height[i + 1]);

        }
        for (int i = 1; i < height.length - 1; i++) {
            int min = Math.min(max_left[i],max_right[i]);
            //只有较小的一列大于当前列的高度才会有水
            if(min>height[i])
                sum += (min - height[i]);
        }
    return sum;
    }
}

71. 简化路径中等

以 Unix 风格给出一个文件的绝对路径，你需要简化它。或者换句话说，将其转换为规范路径。
在 Unix 风格的文件系统中，一个点（.）表示当前目录本身；此外，两个点 （..） 表示将目录切换到上一级（指向父目录）；两者都可以是复杂相对路径的组成部分。更多信息请参阅：Linux / Unix中的绝对路径 vs 相对路径
请注意，返回的规范路径必须始终以斜杠 / 开头，并且两个目录名之间必须只有一个斜杠 /。最后一个目录名（如果存在）不能以 / 结尾。此外，规范路径必须是表示绝对路径的最短字符串。
示例 1：
输入："/home/"
输出："/home"
解释：注意，最后一个目录名后面没有斜杠。
示例 2：
输入："/../"
输出："/"
解释：从根目录向上一级是不可行的，因为根是你可以到达的最高级。
示例 3：
输入："/home//foo/"
输出："/home/foo"
解释：在规范路径中，多个连续斜杠需要用一个斜杠替换。
示例 4：
输入："/a/./b/../../c/"
输出："/c"
示例 5：
输入："/a/../../b/../c//.//"
输出："/c"
示例 6：
输入："/a//b////c/d//././/.."
输出："/a/b/c"

思路：栈

84. 柱状图中最大的矩形困难※※※

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。求在该柱状图中，能够勾勒出来的矩形的最大面积。

以上是柱状图的示例，其中每个柱子的宽度为 1，给定的高度为 [2,1,5,6,2,3]。

图中阴影部分为所能勾勒出的最大矩形面积，其面积为 10 个单位。
输入: [2,1,5,6,2,3]
输出: 10

思路：单调栈

看了以下几篇文章
https://leetcode-cn.com/problems/largest-rectangle-in-histogram/solution/84-by-ikaruga/很好的解释了为什么使用单调栈
https://leetcode-cn.com/problems/largest-rectangle-in-histogram/solution/xiang-jie-dan-diao-zhan-bi-xu-miao-dong-by-sweetie/
https://leetcode-cn.com/problems/largest-rectangle-in-histogram/solution/zhao-liang-bian-di-yi-ge-xiao-yu-ta-de-zhi-by-powc/
遍历每根柱子，以当前柱子 i 的高度作为矩形的高，那么矩形的宽度边界即为向左找到第一个高度小于当前柱体 i 的柱体，向右找到第一个高度小于当前柱体 i 的柱体。
对于每个柱子我们都如上计算一遍以当前柱子作为高的矩形面积，最终比较出最大的矩形面积即可。

class Solution {//执行用时 :15 ms, 在所有 Java 提交中击败了53.09%的用户
    public int largestRectangleArea(int[] heights) {
        int[] tmp = new int[heights.length + 2];
        //在柱体数组的头和尾加了两个高度为 0 的柱体
        //将height中从0开始的，长度为height.length的元素复制到temp从1开始的位置上
        System.arraycopy(heights, 0, tmp, 1, heights.length); 

        Stack<Integer> stack = new Stack <>();
        stack.push(-1);
        int maxarea = 0;
        for (int i = 0; i < tmp.length; ++i) {
            while (stack.peek() != -1 && tmp[stack.peek()] >= tmp[i]){
                maxarea = Math.max(maxarea,tmp[stack.pop()]*(i-stack.peek()-1));
            }
               
            stack.push(i);
        }
        return maxarea;
    }
}

85. 最大矩形困难※※※

给定一个仅包含 0 和 1 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。
输入:
[
["1","0","1","0","0"],
["1","0","1","1","1"],
["1","1","1","1","1"],
["1","0","0","1","0"]
]
输出: 6

出处：https://leetcode-cn.com/problems/maximal-rectangle/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-1-8/

class Solution {
    public int maximalRectangle(char[][] matrix) {//执行用时 :10 ms, 在所有 Java 提交中击败了66.16%的用户
        if (matrix.length == 0) {
        return 0;
    }
    int[] heights = new int[matrix[0].length];
    int maxArea = 0;
    for (int row = 0; row < matrix.length; row++) {
        //遍历每一列，更新高度
        for (int col = 0; col < matrix[0].length; col++) {
            if (matrix[row][col] == '1') {
                heights[col] += 1;
            } else {
                heights[col] = 0;
            }
        }
        //调用上一题的解法，更新函数
        maxArea = Math.max(maxArea, largestRectangleArea(heights));
    }
    return maxArea;
}

public int largestRectangleArea(int[] heights) {
    int maxArea = 0;
    Stack<Integer> stack = new Stack<>();
    int p = 0;
    while (p < heights.length) {
        //栈空入栈
        if (stack.isEmpty()) {
            stack.push(p);
            p++;
        } else {
            int top = stack.peek();
            //当前高度大于栈顶，入栈
            if (heights[p] >= heights[top]) {
                stack.push(p);
                p++;
            } else {
                //保存栈顶高度
                int height = heights[stack.pop()];
                //左边第一个小于当前柱子的下标
                int leftLessMin = stack.isEmpty() ? -1 : stack.peek();
                //右边第一个小于当前柱子的下标
                int RightLessMin = p;
                //计算面积
                int area = (RightLessMin - leftLessMin - 1) * height;
                maxArea = Math.max(area, maxArea);
            }
        }
    }
    while (!stack.isEmpty()) {
        //保存栈顶高度
        int height = heights[stack.pop()];
        //左边第一个小于当前柱子的下标
        int leftLessMin = stack.isEmpty() ? -1 : stack.peek();
        //右边没有小于当前高度的柱子，所以赋值为数组的长度便于计算
        int RightLessMin = heights.length;
        int area = (RightLessMin - leftLessMin - 1) * height;
        maxArea = Math.max(area, maxArea);
    }
    return maxArea;
    }
}

94. 二叉树的中序遍历中等

给定一个二叉树，返回它的中序遍历。

进阶: 递归算法很简单，你可以通过迭代算法完成吗？

思路：迭代+栈

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {//执行用时 :1 ms, 在所有 Java 提交中击败了49.48%的用户
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        while(root != null || stack.size() > 0){
            if(root != null){
                //不断往左子树方向走，每走一次就将当前节点保存到栈中，这是模拟递归的调用
                stack.push(root);
                root = root.left;
            }else{
                //当前节点为空，说明左边走到头了，从栈中弹出节点并保存，然后转向右边节点，继续上面整个过程
                TreeNode temp = stack.pop();//pop()函数返回栈顶的元素，并且将该栈顶元素出栈
                res.add(temp.val);
                root = temp.right;
            }
        }
    return res;
    }
}

144. 二叉树的前序遍历中等

给定一个二叉树，返回它的 *前序 *遍历。

进阶: 递归算法很简单，你可以通过迭代算法完成吗？

思路：迭代+栈

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {//执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if(root == null)
            return res;

        Deque<TreeNode> stack = new ArrayDeque<>();  // 创建一个栈,官方推荐利用Deque
        stack.push(root);//根节点入栈

        while (!stack.isEmpty()){
            // 1.节点出栈,访问节点, 加入ArrayList中
            TreeNode node = stack.poll();
            res.add(node.val);

            //之所以先加入右孩子再加入左孩子是利用栈后入先出的原则
            // 2.若右孩子节点非空, 则将右孩子入栈
            if(node.right != null)    
                stack.push(node.right);
            
            // 3.若左孩子节点非空, 则将左孩子入栈
            if(node.left != null)   
                stack.push(node.left);
  
        }
        return res;
    }
}

145. 二叉树的后序遍历困难

给定一个二叉树，返回它的 后序遍历。
示例:
输入: [1,null,2,3]
输出: [3,2,1]
进阶: 递归算法很简单，你可以通过迭代算法完成吗？

思路：迭代+栈

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {执行用时：1 ms, 在所有 Java 提交中击败了56.90%的用户
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if(root == null)
            return res;

        Deque<TreeNode> stack = new ArrayDeque<>();  // 创建一个栈,官方推荐利用Deque
        stack.push(root);//根节点入栈

        while (!stack.isEmpty()){
            // 1.节点出栈,保存节点值
            TreeNode node = stack.poll();
            res.add(node.val);
            // 2.左孩子节点入栈
            if(node.left != null)   
                stack.push(node.left);
            // 3.右孩子节点入栈
            if(node.right != null)    
                stack.push(node.right);
            
        }
        Collections.reverse(res);//再逆序访问节点
        return res;
    }
}

150. 逆波兰表达式求值中等

根据 逆波兰表示法，求表达式的值。
有效的运算符包括 +, -, *, / 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。
说明：
整数除法只保留整数部分。
给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。
示例 ：
输入: ["2", "1", "+", "3", " * "]
输出: 9
解释: 该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9
逆波兰表达式：是一种后缀表达式，所谓后缀就是指算符写在后面。
平常使用的算式则是一种中缀表达式，如 ( 1 + 2 ) * ( 3 + 4 ) 。
该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * ) 。
逆波兰表达式主要有以下两个优点：
去掉括号后表达式无歧义，上式即便写成 1 2 + 3 4 + *也可以依据次序计算出正确结果。
适合用栈操作运算：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中。

思路：栈

class Solution {//执行用时：6 ms, 在所有 Java 提交中击败了89.88%的用户
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();
        int num1,num2;
        for(String s:tokens){
            switch(s){
                case "+":
                    num2 = stack.pop();
                    num1 = stack.pop();
                    stack.push(num1 + num2);
                    break;
                case "-":
                    num2 = stack.pop();
                    num1 = stack.pop();
                    stack.push(num1 - num2);
                    break;
                case "*":
                    num2 = stack.pop();
                    num1 = stack.pop();
                    stack.push(num1 * num2);
                    break;
                case "/":
                    num2 = stack.pop();
                    num1 = stack.pop();
                    stack.push(num1 / num2);
                    break;
                default:
                    stack.push(Integer.valueOf(s));
                    break;
            }
        }
    return stack.pop();
    }
}