739. 每日温度【单调栈】

给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。

---

思路：
单调栈，注意弹出条件。
下面介绍一下单调栈：
  单调栈（Monotonic Stack）是一种用于解决一些与查找下一个较大或较小元素相关的问题的数据结构和算法。单调栈通常用于数组或链表等序列数据的处理，其主要特点是栈内元素具有单调性，可以是单调递增或单调递减。

  单调栈的基本思想是在遍历序列的过程中，维护一个栈，栈内元素按照某种单调性排列，通常是单调递增或单调递减。当新元素需要入栈时，会与栈顶元素比较，根据问题的要求进行不同的操作，例如弹出栈顶元素、计算栈顶元素与新元素之间的距离等。单调栈的目的是在O(N)的时间复杂度内解决与查找下一个较大或较小元素相关的问题，而不需要使用嵌套循环来搜索。

单调栈常见的应用包括：

**下一个较大元素**：给定一个数组，对于每个元素，找到数组中下一个比它大的元素的位置。这个问题可以使用单调递减栈来解决。

**下一个较小元素**：与上一个问题相似，但是需要找到下一个较小的元素。这个问题可以使用单调递增栈来解决。

**找到数组中的某个元素的左右边界**：给定一个数组和一个目标元素，找到该元素在数组中的左右边界。这可以通过使用两个单调栈（一个用于查找左边界，另一个用于查找右边界）来实现。

**柱状图中的最大矩形面积**：给定一个柱状图，找到其中的最大矩形面积。这个问题可以使用单调递增栈来解决，用于维护柱子的递增高度序列。

滑动窗口最大值：给定一个数组和一个窗口大小，找到每个窗口中的最大值。这可以通过使用单调递减栈来优化窗口内元素的查找。
1
2
3
4
5
6
7
8
9
10
11

  总之，单调栈是一种强大的数据结构和算法，用于解决多种与查找下一个较大或较小元素相关的问题，通常能够在O(N)的时间复杂度内完成这些操作。在算法竞赛和实际应用中，单调栈常常被用来提高算法的效率。

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int n = temperatures.length;
        int[] ans = new int[n];
        Deque<int[]> stack = new ArrayDeque();
        stack.push(new int[]{-1, Integer.MAX_VALUE});
        for(int i=0; i<n; i++) {
            while(temperatures[i]>stack.peek()[1]) {
                int idx = stack.peek()[0];
                ans[idx] = i - idx;
                stack.pop();
            }
            stack.push(new int[]{i, temperatures[i]});
        }

        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18