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 {//執(zhí)行用時：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 {//執(zhí)行用時：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 個非負整數(shù)表示每個寬度為 1 的柱子的高度圖，計算按此排列的柱子，下雨之后能接多少雨水。


上面是由數(shù)組 [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)

對于數(shù)組中的每個元素，下雨后水能達到的最高位置，等于兩邊最大高度的較小值減去當前高度的值。為了找到最大值每次都要向左和向右掃描一次。

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;
    }
}
思路二：動態(tài)規(guī)劃，時間復雜度O(n)

在按列求解的暴力法中，對于每一列，我們求它左邊最高的墻和右邊最高的墻，都是重新遍歷一遍所有高度。為了降低時間復雜度，定義兩個數(shù)組，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 風格給出一個文件的絕對路徑，你需要簡化它?；蛘邠Q句話說，將其轉(zhuǎn)換為規(guī)范路徑。
在 Unix 風格的文件系統(tǒng)中，一個點（.）表示當前目錄本身；此外，兩個點 （..） 表示將目錄切換到上一級（指向父目錄）；兩者都可以是復雜相對路徑的組成部分。更多信息請參閱：Linux / Unix中的絕對路徑 vs 相對路徑
請注意，返回的規(guī)范路徑必須始終以斜杠 / 開頭，并且兩個目錄名之間必須只有一個斜杠 /。最后一個目錄名（如果存在）不能以 / 結(jié)尾。此外，規(guī)范路徑必須是表示絕對路徑的最短字符串。
示例 1：
輸入："/home/"
輸出："/home"
解釋：注意，最后一個目錄名后面沒有斜杠。
示例 2：
輸入："/../"
輸出："/"
解釋：從根目錄向上一級是不可行的，因為根是你可以到達的最高級。
示例 3：
輸入："/home//foo/"
輸出："/home/foo"
解釋：在規(guī)范路徑中，多個連續(xù)斜杠需要用一個斜杠替換。
示例 4：
輸入："/a/./b/../../c/"
輸出："/c"
示例 5：
輸入："/a/../../b/../c//.//"
輸出："/c"
示例 6：
輸入："/a//b////c/d//././/.."
輸出："/a/b/c"

思路：棧

84. 柱狀圖中最大的矩形困難※※※

給定 n 個非負整數(shù)，用來表示柱狀圖中各個柱子的高度。每個柱子彼此相鄰，且寬度為 1 。求在該柱狀圖中，能夠勾勒出來的矩形的最大面積。


以上是柱狀圖的示例，其中每個柱子的寬度為 1，給定的高度為 [2,1,5,6,2,3]。

圖中陰影部分為所能勾勒出的最大矩形面積，其面積為 10 個單位。
輸入: [2,1,5,6,2,3]
輸出: 10

思路：單調(diào)棧

看了以下幾篇文章
https://leetcode-cn.com/problems/largest-rectangle-in-histogram/solution/84-by-ikaruga/很好的解釋了為什么使用單調(diào)棧
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 {//執(zhí)行用時 :15 ms, 在所有 Java 提交中擊敗了53.09%的用戶
    public int largestRectangleArea(int[] heights) {
        int[] tmp = new int[heights.length + 2];
        //在柱體數(shù)組的頭和尾加了兩個高度為 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) {//執(zhí)行用時 :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;
            }
        }
        //調(diào)用上一題的解法，更新函數(shù)
        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();
        //右邊沒有小于當前高度的柱子，所以賦值為數(shù)組的長度便于計算
        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 {//執(zhí)行用時 :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){
                //不斷往左子樹方向走，每走一次就將當前節(jié)點保存到棧中，這是模擬遞歸的調(diào)用
                stack.push(root);
                root = root.left;
            }else{
                //當前節(jié)點為空，說明左邊走到頭了，從棧中彈出節(jié)點并保存，然后轉(zhuǎn)向右邊節(jié)點，繼續(xù)上面整個過程
                TreeNode temp = stack.pop();//pop()函數(shù)返回棧頂?shù)脑兀⑶覍⒃摋ｍ斣爻鰲?                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 {//執(zhí)行用時：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<>();  // 創(chuàng)建一個棧,官方推薦利用Deque
        stack.push(root);//根節(jié)點入棧

        while (!stack.isEmpty()){
            // 1.節(jié)點出棧,訪問節(jié)點, 加入ArrayList中
            TreeNode node = stack.poll();
            res.add(node.val);

            //之所以先加入右孩子再加入左孩子是利用棧后入先出的原則
            // 2.若右孩子節(jié)點非空, 則將右孩子入棧
            if(node.right != null)    
                stack.push(node.right);
            
            // 3.若左孩子節(jié)點非空, 則將左孩子入棧
            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 {執(zhí)行用時：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<>();  // 創(chuàng)建一個棧,官方推薦利用Deque
        stack.push(root);//根節(jié)點入棧

        while (!stack.isEmpty()){
            // 1.節(jié)點出棧,保存節(jié)點值
            TreeNode node = stack.poll();
            res.add(node.val);
            // 2.左孩子節(jié)點入棧
            if(node.left != null)   
                stack.push(node.left);
            // 3.右孩子節(jié)點入棧
            if(node.right != null)    
                stack.push(node.right);
            
        }
        Collections.reverse(res);//再逆序訪問節(jié)點
        return res;
    }
}

150. 逆波蘭表達式求值中等

根據(jù) 逆波蘭表示法，求表達式的值。
有效的運算符包括 +, -, *, / 。每個運算對象可以是整數(shù)，也可以是另一個逆波蘭表達式。
說明：
整數(shù)除法只保留整數(shù)部分。
給定逆波蘭表達式總是有效的。換句話說，表達式總會得出有效數(shù)值且不存在除數(shù)為 0 的情況。
示例 ：
輸入: ["2", "1", "+", "3", " * "]
輸出: 9
解釋: 該算式轉(zhuǎn)化為常見的中綴算術表達式為：((2 + 1) * 3) = 9
逆波蘭表達式：是一種后綴表達式，所謂后綴就是指算符寫在后面。
平常使用的算式則是一種中綴表達式，如 ( 1 + 2 ) * ( 3 + 4 ) 。
該算式的逆波蘭表達式寫法為 ( ( 1 2 + ) ( 3 4 + ) * ) 。
逆波蘭表達式主要有以下兩個優(yōu)點：
去掉括號后表達式無歧義，上式即便寫成 1 2 + 3 4 + *也可以依據(jù)次序計算出正確結(jié)果。
適合用棧操作運算：遇到數(shù)字則入棧；遇到算符則取出棧頂兩個數(shù)字進行計算，并將結(jié)果壓入棧中。

思路：棧
class Solution {//執(zhí)行用時：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();
    }
}
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務。

友情鏈接更多精彩內(nèi)容