LC.P739[每日温度]

方法一：单调栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int n = temperatures.length;
        Deque<Integer> stack = new ArrayDeque<>();
        int[] ans = new int[n];
        for (int i = 0; i < n; ++i) {
            while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
                int index = stack.pop();
                ans[index] = i - index;
            }
            stack.push(i);
        }
        return ans;
    }
}
  • 时间复杂度：$O(n)$
  • 空间复杂度：$O(n)$

方法二：手写栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int n = temperatures.length;
        int[] ans = new int[n], stack = new int[n];
        int tt = -1;
        for (int i = 0; i < n; ++i) {
            while (tt > -1 && temperatures[i] > temperatures[stack[tt]]) {
                int index = stack[tt--];
                ans[index] = i - index;
            }
            stack[++tt] = i;
        }
        return ans;
    }
}
  • 时间复杂度：$O(n)$
  • 空间复杂度：$O(n)$