Neetcode 150 — Stack

AShiou

5 min read

·

Oct 13, 2026

--

Listen

Share

最近為了練習刷題，開始寫 Neetcode 150。以下是我的刷題筆記，主要以 JAVA 來練習，分類及題目來自 Neetcode。

1. Valid Parentheses

// 1. Stack
// 如果遇到左邊的括號，就放進 stack；如果遇到右邊的括號，就和 stack 的比較看能不能湊對
// ex. s = "([{}])"
// '('-> stack:"("
// '['-> stack:"(["
// '{'-> stack: "([{"
// '}'-> stack: "([", '{' 和 '}'配對
// ']'-> stack: "(", '[' 和 ']'配對
// ')'-> stack: "", '(' 和 ')' 配對，並且 stack 為空 -> return true
//
// 假設 s 長度為 n
// Time complexity: O(n)
// Space complexity: O(n)
//
// Dry run
// "([{}])" -> true
// "()[]{}" -> true
// "" -> true
// ")" -> false
// "{]" -> false
class Solution {
    public boolean isValid(String s) {
        ArrayDeque<Character> stack = new ArrayDeque<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '{' || c == '[' || c == '(') {
                stack.push(c);
                continue;
            }
            if (stack.isEmpty()) {
                return false;
            }
            char left = stack.pop();
            if ((left == '{' && c != '}') ||
                (left == '[' && c != ']') ||
                (left == '(' && c != ')')) {
                return false;
            }
        }
        return stack.isEmpty();
    }
}

2. Min Stack

// 1. Stack
// 一個 stack 存 value, 一個 stack 存當下的最小值
// 支持 push, pop, top, min 都是 O(1)
//
// Time complexity: O(1)
// Space complexity: O(n)
//
// Dry run
// push1, push2, push0, getMin, pop, top, getMin
class MinStack {

    private ArrayDeque<Integer> stackVal;
    private ArrayDeque<Integer> stackMinVal;

    public MinStack() {
        stackVal = new ArrayDeque<>();
        stackMinVal = new ArrayDeque<>();
    }
    
    public void push(int val) {
        stackVal.push(val);
        if (!stackMinVal.isEmpty()) {
            stackMinVal.push(Math.min(stackMinVal.peek(), val));
        } else {
            stackMinVal.push(val);
        }
    }
    
    public void pop() {
        stackVal.pop();
        stackMinVal.pop();
    }
    
    public int top() {
        return stackVal.peek();
    }
    
    public int getMin() {
        return stackMinVal.peek();
    }
}

3. Evaluate Reverse Polish Notation

// 1. Stack
// 如果遇到數字，則放到 stack；如果遇到運算符號，則pop兩個數字做運算
// ["1","2","+","3","*","4","-"]
// "1" -> stack:1
// "2" -> stack:1,2
// "+" -> stack:empty, 1+2=3, push to stack:3
// "3" -> stack:3,3
// "*" -> stack:empty, 3*3=9, push to stack:9
// "4" -> stack:9,4
// "-" -> stack:empty, 9-4=5
//
// 假設有 n 個 token
// Time complexity: O(n)
// Space complexity: O(n)
//
// Dry run
// ["1","2","+","3","*","4","-"] -> 5
class Solution {
    public int evalRPN(String[] tokens) {
        ArrayDeque<Integer> stack = new ArrayDeque<>();
        for (String token : tokens) {
            if (token.equals("+")) {
                int b = stack.pop();
                int a = stack.pop();
                stack.push(a + b);
            } else if (token.equals("-")) {
                int b = stack.pop();
                int a = stack.pop();
                stack.push(a - b);
            } else if (token.equals("*")) {
                int b = stack.pop();
                int a = stack.pop();
                stack.push(a * b);
            } else if (token.equals("/")) {
                int b = stack.pop();
                int a = stack.pop();
                stack.push(a / b);
            } else {
                stack.push(Integer.parseInt(token));
            }
        }
        return stack.pop();
    }
}

4. Daily Temperatures

// 1. Brute force
// for loop 每一個數值，裡面再 for loop 往後找比自己大的值
// ex. [30,38,30,36,35,40,28]
// [30] -> 38
// [38] -> 30x, 36x, 35x, 40v
// [30] -> 36
// [36] -> 35x, 40v
// [35] -> 40
// [40] -> 28x
// [28] -> x
//
// 假設 temperatures 有 n 個數值
// Time complexity: O(n^2)
// Space complexity: O(n) -> 存結果

// 2. Stack
// for loop 每個數字，把數字的 index 放到 stack，
// 如果接下來遇到的數字比自己大，就 pop 並記錄結果
// stack 從底部到top的順序會因此變成從大到小
// 最後再把 stack 剩下的值 pop，並記錄結果為 0
//
// ex. [30,38,30,36,35,40,28]
// [30] -> push 30, stack:[0(30)]
// [38] -> pop 30, 紀錄result[0]=1, push 38, stack:[1(38)]
// [30] -> push 30, stack:[1(38), 2(30)]
// [36] -> pop 30, 紀錄result[2]=1, push 36, stack:[1(38),3(36)]
// [35] -> push 35, stack:[1(38),3(36),4(35)]
// [40] -> pop 35,紀錄result[4]=1；pop 36,紀錄result[3]=2；
//         pop 38,紀錄result[1]=4；push 40, stack:[5(40)]
// [28] -> push 28, stack:[5(40),6(28)]
// pop 28, 紀錄result[6]=0, pop 40, 紀錄result[5]=0
//
// Time complexity: O(n)
// Space complexity: O(n)
//
// Dry run
// [] -> []
// [1] -> [0]
// [30,38,30,36,35,40,28] -> [1,4,1,2,1,0,0]
class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int[] result = new int[temperatures.length];
        ArrayDeque<Integer> stack = new ArrayDeque<>();
        for (int i = 0; i < temperatures.length; i++) {
            while (!stack.isEmpty() && temperatures[stack.peek()] < temperatures[i]) {
                int index = stack.pop();
                result[index] = i - index;
            }
            stack.push(i);
        }
        while(!stack.isEmpty()) {
            int index = stack.pop();
            result[index] = 0;
        }
        return result;
    }
}

5. Car Fleet

// 1. Brute force + sort
// 因為不可以超車，頂多一起走
// ex. target = 10, position = [4,1,0,7], speed = [2,2,1,1]
// 如果先 sort 變成 position=[0,1,4,7],speed=[1,2,2,1]
// 1st run: position=[1,3,6,8]，還是維持順序，代表沒有形成 car fleet
// 2nd run: position=[2,5,8,9]，還是維持順序，代表沒有形成 car fleet
// 3rd run: position=[3,7,10,10]，2和3形成car fleet
// 4rd run: position=[4,8]
// 5rd run: position=[5,10]，1完成，是一個 car fleet
// 6rd run: position=[6]，之後會是一個 cat fleet
// result = 3
// 假設 position 有 n 個，target 為 k
// Time complexity: O(nlogn+nk)
// Space complexity: O(1)

// 2.sort + 計算每個car的時間
// ex. target = 10, position = [4,1,0,7], speed = [2,2,1,1]
// 如果先 sort 變成 position=[0,1,4,7],speed=[1,2,2,1]
// 計算每個 position 到終點需要多少時間
// [10,5,3,3] -> 從後往前看，如果時間小於等於前面的，代表會形成 car fleet；
//               時間比前面的大，會是另一個 car fleet
//
// Time complexity: O(nlogn)
// Space complexity: O(n)
//
// Dry run
// target = 10, position = [4,1,0,7], speed = [2,2,1,1]
// target=10, position=[1,2,3,4], speed=[4,3,2,1]
class Solution {
    public int carFleet(int target, int[] position, int[] speed) {
        int n = position.length;
        int[][] car = new int[n][2];
        for (int i = 0; i < n; i++) {
            car[i][0] = position[i];
            car[i][1] = speed[i];
        }

        Arrays.sort(car, (a, b) -> a[0] - b[0]);

        int fleet = 0;
        double prevTime = 0;
        for (int i = n - 1; i >= 0; i--) {
            double time = (double)(target - car[i][0]) / car[i][1];
            if (time > prevTime) {
                fleet++;
                prevTime = time;
            }
        } 
        return fleet;
    }
}

6. Largest Rectangle In Histogram

// 1. Brute Force
// for loop 從第一個值開始，裡面再一個 for loop 看最大可以多大
// ex. heights = [7,1,7,2,2,4]
// [7] -> max=7
// [7,1] -> 1*2=2,max=7
// [7,1,7] -> 1*3=3, max=7
// [7,1,7,2] -> 1*4=4, max=7
// ...
// [1] -> 1*1=1, max=7
// [1,7] -> 1*2=2, max=7
// ...
// 假設 heights 有 n 個
// Time complexity: O(n^2)
// Space complexity: O(1)

// 2. Stack
// 當你左右的柱子都比你小時，代表現在是最佳解
// ex. heights = [7,1,7,2,2,4]
// [7] -> push 7, stack:[0(7)]
// [1] -> 1比7小，代表7的左右柱子都比7小，pop 7, 7*1=7, max=7, push 1, stack:[1(1)]
// [7] -> push 7, stack:[1(1),2(7)]
// [2] -> 2比7小，代表7的左右柱子都比7小，pop 7, 7*1=7, max=7, push 2, stack:[1(1), 3(2)]
// [2] -> push 2, stack:[1(1), 3(2), 4[2]]
// [4] -> push 4, stack:[1(1),3(2),4(2),5(4)]
// [0](多放的右邊柱子) -> 4比0小，pop4,4*1=4,max=7；
//                      2比0小，pop2,2*2=4(左柱為3(2),右柱為6(0)), max=7
//                      2比0小，pop2,2*4=8(左柱為1(1),右柱為6(0)), max=8
//                      1比0小，pop1,1*6=6(右柱為6(0)), max=8
//
// Time complexity: O(n)
// Space complexity: O(n)
//
// Dry run
// [7,1,7,2,2,4] -> 8
// [] -> 0
// [1] -> 1
class Solution {
    public int largestRectangleArea(int[] heights) {
        int max = 0;
        ArrayDeque<Integer> stack = new ArrayDeque<>();
        for (int i = 0; i <= heights.length; i++) {
            int rightH = (i == heights.length) ? 0 : heights[i];
            while(!stack.isEmpty() && heights[stack.peek()] > rightH) {
                int h = heights[stack.pop()];
                int width;
                if (stack.isEmpty()) {
                    width = i;
                } else {
                    width = i - stack.peek() - 1;
                }
                max = Math.max(max, h * width);
            }
            stack.push(i);
        }
        return max;
    }
}