Ming
0%

LeetCode-739

Posted on Edited on In

题目

Snipaste_2020-12-03_09-55-26.png

结果

Snipaste_2020-12-03_10-43-00.png

代码

遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int[] dailyTemperatures(int[] T) {
        int[] ans = new int[T.length];
        for (int i = 0; i < T.length; i++) {
            // 站在巨人的肩膀上
            if (i != 0 && T[i] == T[i - 1] && ans[i - 1] != 0) {
                ans[i] = ans[i - 1] - 1;
                continue;
            }
            ans[i] = goStraight(T, i);
        }
        return ans;
    }

    private int goStraight(int[] T, int index) {
        for (int i = index + 1; i < T.length; i++) {
            if (T[i] > T[index]) {
                return i - index;
            }
        }
        return 0;
    }
}

单调栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int[] dailyTemperatures(int[] T) {
        int[] ans = new int[T.length];
        Deque<Integer> stack = new LinkedList<>();
        for (int i = 0; i < T.length; i++) {
            // 使栈中的元素从栈底到栈顶递减
            while (!stack.isEmpty() && T[i] > T[stack.peek()]) {
                int index = stack.pop();
                ans[index] = i - index;
            }
            stack.push(i);
        }
        // 此时栈中还剩最后一个元素，但最后一个元素对应的ans必然是0，不必考虑
        return ans;
    }
}

复杂度

遍历：

  • 时间复杂度：O（n²）

  • 空间复杂度：O（n）

单调栈：

  • 时间复杂度：O（n），所有元素遍历一遍，进栈一次，出栈一次。
  • 空间复杂度：O（n）