力扣刷题day50|739每日温度、496下一个更大元素 I

739. 每日温度

力扣题目链接

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

示例 1:

输入: temperatures = [73,74,75,71,69,72,76,73]
输出: [1,1,4,2,1,1,0,0]
1
2

示例 2:

输入: temperatures = [30,40,50,60]
输出: [1,1,1,0]
1
2

示例 3:

输入: temperatures = [30,60,90]
输出: [1,1,0]
1
2

暴力思路

暴力解法，两层for循环，第一个for循环每个天数，第二个for找该天温度后面的更高温

单调栈思路

什么时候用单调栈？

• 怎么能想到用单调栈呢？ 什么时候用单调栈呢？

通常是一维数组，要寻找任一个元素的右边或者左边第一个比自己大或者小的元素的位置，此时我们就要想到可以用单调栈了。

例如本题其实就是要找到一个元素右边第一个比自己大的元素。

• 那么单调栈的原理是什么呢？为什么**时间复杂度是O(n)**就可以找到每一个元素的右边第一个比它大的元素位置呢？

单调栈的本质是空间换时间，因为在遍历的过程中需要用一个栈来记录右边第一个比当前元素高的元素，优点是只需要遍历一次。

• 在使用单调栈的时候首先要明确如下几点：

1. 单调栈里存放的元素是什么？

单调栈里**只需要存放元素的下标i**就可以了，如果需要使用对应的元素，直接T[i]就可以获取。

2. 单调栈里元素是递增呢？ 还是递减呢？

注意一下顺序为从栈顶到栈底的顺序（因为说从左到右或者从前到后，不知道栈顶和栈底是哪）

这道题中，从栈顶到栈底的顺序是递增循序，因为只有递增的时候，加入一个元素i，才知道栈顶元素在数组中右面第一个比栈顶元素大的元素是i。

解题思路

使用单调栈主要有三个判断条件。

• 当前遍历的元素T[i]小于栈顶元素T[st.top()]的情况
• 当前遍历的元素T[i]等于栈顶元素T[st.top()]的情况
• 当前遍历的元素T[i]大于栈顶元素T[st.top()]的情况

用示例1的temperatures = [73, 74, 75, 71, 71, 72, 76, 73]为例来逐步分析，输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]来画图解题

首先先将第一个遍历元素下标加入单调栈

加入T[1] = 74，因为T[1] > T[0]（当前遍历的元素T[i]大于栈顶元素T[st.top()]的情况），而我们要保持一个递增单调栈（从栈顶到栈底），所以将T[0]弹出，T[1]加入，此时result数组可以记录了，result[0] = 1，即T[0]右面第一个比T[0]大的元素是T[1]。

加入T[2]，同理，T[1]弹出

加入T[3]，T[3] < T[2] （当前遍历的元素T[i]小于栈顶元素T[st.top()]的情况），加T[3]加入单调栈。

加入T[4]，T[4] == T[3] （当前遍历的元素T[i]等于栈顶元素T[st.top()]的情况），此时依然要加入栈，不用计算距离，因为我们要求的是右面第一个大于本元素的位置，而不是大于等于！

加入T[5]，T[5] > T[4] （当前遍历的元素T[i]大于栈顶元素T[st.top()]的情况），将T[4]弹出，同时计算距离，更新result

T[4]弹出之后， T[5] > T[3] （当前遍历的元素T[i]大于栈顶元素T[st.top()]的情况），将T[3]继续弹出，同时计算距离，更新result

直到发现T[5]小于T[st.top()]，终止弹出，将T[5]加入单调栈

加入T[6]，同理，需要将栈里的T[5]弹出

继续弹出T[2]

此时栈里只剩下了T[6]

加入T[7]，T[7] < T[6]直接入栈，这就是最后的情况，result数组也更新完了。

result[6] 和 result[7]初始化的时候就为0（如果result没有更新，说明这个元素右面没有更大的了，也就是为0）

完整代码：

public int[] dailyTemperatures(int[] temperatures) {
    int[] res = new int[temperatures.length];

    // 定义单调栈
    Deque<Integer> stack = new LinkedList<>();
    // 空栈直接入栈
    stack.push(0);
    // 遍历每个温度
    for (int i = 1; i < temperatures.length; i++) {
        if (temperatures[i] <= temperatures[stack.peek()]) { // 如果当前遍历元素小于等于栈顶的元素
            stack.push(i);
        }else {
            // 找到大于栈内元素的时候
            while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
                res[stack.peek()] = i - stack.peek();
                stack.pop();
            }
            stack.push(i);
        }
    }

    return res;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

注：想把LinkedList当做集合list，那么应该用add/remove，如果想用作队列，则使用offer/poll，如果用作栈，则使用push/pop，如果用作双端队列，则使用offerFirst/offerLast/pollFirst/pollLast。根据语义使用，就不会发生：我想删队尾，结果删了队头这种事了。

496. 下一个更大元素 I

力扣题目链接

nums1 中数字 x 的 下一个更大元素 是指 x 在 nums2 中对应位置 右侧 的 第一个 比 x 大的元素。

给你两个 没有重复元素 的数组 nums1 和 nums2 ，下标从 0 开始计数，其中nums1 是 nums2 的子集。

对于每个 0 <= i < nums1.length ，找出满足 nums1[i] == nums2[j] 的下标 j ，并且在 nums2 确定 nums2[j] 的 下一个更大元素 。如果不存在下一个更大元素，那么本次查询的答案是 -1 。

返回一个长度为 nums1.length 的数组 ans 作为答案，满足 ans[i] 是如上所述的 下一个更大元素 。

示例 1：

输入：nums1 = [4,1,2], nums2 = [1,3,4,2].
输出：[-1,3,-1]
解释：nums1 中每个值的下一个更大元素如下所述：
- 4 ，用加粗斜体标识，nums2 = [1,3,4,2]。不存在下一个更大元素，所以答案是 -1 。
- 1 ，用加粗斜体标识，nums2 = [1,3,4,2]。下一个更大元素是 3 。
- 2 ，用加粗斜体标识，nums2 = [1,3,4,2]。不存在下一个更大元素，所以答案是 -1 。
1
2
3
4
5
6

示例 2：

输入：nums1 = [2,4], nums2 = [1,2,3,4].
输出：[3,-1]
解释：nums1 中每个值的下一个更大元素如下所述：
- 2 ，用加粗斜体标识，nums2 = [1,2,3,4]。下一个更大元素是 3 。
- 4 ，用加粗斜体标识，nums2 = [1,2,3,4]。不存在下一个更大元素，所以答案是 -1 。
1
2
3
4
5

思路

由题意可以指导要定义一个和nums1一样大小的数组result来存放结果。

• 这个result数组初始化应该为多少呢？

题目说如果不存在对应位置就输出 -1 ，所以result数组如果某位置没有被赋值，那么就应该是是-1，所以就初始化为-1。

在遍历nums2的过程中，我们要判断nums2[i]是否在nums1中出现过，因为最后是要根据nums1元素的下标来更新result数组。

注意题目中说是两个没有重复元素 的数组 nums1 和 nums2。

没有重复元素，我们就可以用map来做映射了。根据数值快速找到下标，还可以判断nums2[i]是否在nums1中出现过。

// 把nums1装入map
HashMap<Integer, Integer> hashMap = new HashMap<>();
for (int i = 0 ; i< nums1.length ; i++){
    hashMap.put(nums1[i],i);
}
1
2
3
4
5

单调栈

• 为什么要用单调栈呢？因为我们要找nums1中元素的右边第一个更大的元素，而nums1中的元素都是存在于nums2中的。
• 所以当我们发现nums2中的某个元素是大于前面元素的时候时，就判断这个元素是不是同样存在于nums1中，如果在nums1中，那就可以记录下当前的大元素到结果数组中

使用单调栈，首先要想单调栈是从大到小还是从小到大。

栈头到栈底的顺序，要从小到大，也就是保持栈里的元素为递增顺序。只要保持递增，才能找到右边第一个比自己大的元素。

接下来就要分析如下三种情况，将nums2的元素入栈：

1. 情况一：当前遍历的元素T[i]小于栈顶元素T[st.top()]的情况

此时满足递增栈（栈头到栈底的顺序），所以直接入栈。

2. 情况二：当前遍历的元素T[i]等于栈顶元素T[st.top()]的情况

如果相等的话，依然直接入栈，因为我们要求的是右边第一个比自己大的元素，而不是大于等于！

3. 情况三：当前遍历的元素T[i]大于栈顶元素T[st.top()]的情况

此时如果入栈就不满足递增栈了，这也是找到右边第一个比自己大的元素的时候。

判断栈顶元素是否在nums1里出现过，（注意栈里的元素是nums2的元素），如果出现过，开始记录结果。

记录结果的逻辑是：此时栈顶元素在nums2中右面第一个大的元素是nums2[i]即当前遍历元素。

完整代码

public int[] nextGreaterElement(int[] nums1, int[] nums2) {
    int[] res = new int[nums1.length];
    Arrays.fill(res, -1);

    // 把nums1装入map  key:下标元素，value：下标
    HashMap<Integer, Integer> map = new HashMap<>();
    for (int i = 0 ; i < nums1.length ; i++){
        map.put(nums1[i], i);
    }

    // 定义单调栈
    Deque<Integer> stack = new LinkedList<>();
    stack.push(0);
    for (int i = 1; i < nums2.length; i++) {
        if (nums2[i] <= nums2[stack.peek()]) {
            stack.push(i);
        }else {
            while (!stack.isEmpty() && nums2[i] > nums2[stack.peek()]) {
                // 看nums1里是否存在这个元素
                if (map.containsKey(nums2[stack.peek()])) {
                    // 根据map找到nums2[stack.peek()] 在 nums1中的下标
                    int index = map.get(nums2[stack.peek()]);
                    res[index] = nums2[i];
                }
                stack.pop();
            }
            stack.push(i);
        }
    }

    return res;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32