739. Daily Temperatures

naive - two pointers

T: O(n^2)

T: O(n), with ans result

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int n = temperatures.length;
        int[] res = new int[n];
        int i = 0;
        int j = 1;
        while (i < n && j < n) {
            while (j < n && temperatures[j] <= temperatures[i]) {
                j++;
            }
            if (j < n) {
                res[i] = j-i;
            }
            i++;
            j = i+1;
        }
        return res;
    }
}
/*
 1. two pinters
 2. if find, the ans is (j-i), if next i, j set to i the same position
 
 
 [55,38,53,81,61,93,97,32,43,78]
                    i
                          j
  3   1  1  2  1 1  

*/

mono stack (decresing, 注意要判斷 decresing or increasing

[73,74,75,71,69,72,76,73]
 [1,1,  4, 2, 1, 1,0,0]
 
 
[ 75,71,69] in decresing stack , meets 72 > peek(), start to pop

T: O(n)

S: O(n), with ans result and stack

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int n = temperatures.length;
        int[] res = new int[n];
        Deque<Integer> stack = new ArrayDeque<>();
        
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
                int idx = stack.pop();
                res[idx] = i - idx;
            }
            stack.push(i);
        }
        return res;
    }
}

Array, Optimized Space

no stack

T: O(n)

S: O(n), with ans result

https://leetcode.com/problems/daily-temperatures/solution/