739. Daily Temperatures - Medium

題目連結

想法

• 暴力解法好像也不會到太差，每項都往後找到比自己大的，每項最多n次，總共m項，那就是$n^2$
• 除此之外沒什麼想法

思路

看了官神的影片發現這題又是一個新的技巧，Monotonic stack

Github: 連結

Code

這部分我參考Neetcode大大的，比較簡潔清楚

Neetcode原始程式碼: 連結

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        // Index storage
        Stack<Integer> stack = new Stack<>();
        int[] res = new int[temperatures.length];

        // Loop through temperatures
        for (int i = 0; i < temperatures.length; ++i) {
            // When current temp is higher than the last remaining one
            while (!stack.isEmpty() &&
                temperatures[i] > temperatures[stack.peek()]
                ) {
                    int prevDay = stack.pop();
                    res[prevDay] = i - prevDay;
                }
            // Add current day index to the stack
            stack.add(i);
        }

        return res;

    }
}

2024/04/12

• 忘了monotonic stack

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        // Index storage
        Stack<Integer> stack = new Stack<>();
        int[] res = new int[temperatures.length];

        for (int i = 0; i < temperatures.length; ++i) {
            // Stack
            while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
                res[stack.peek()] = i - stack.pop();
            }
            stack.push(i);
        }
        return res;
    }
}