【每日算法Day 11】每日温度：单调栈的使用

题目链接

LeetCode 739. 每日温度 (opens new window)

题目描述

请根据每日 气温 列表，重新生成一个列表。对应位置的输出为：要想观测到更高的气温，至少需要等待的天数。如果气温在这之后都不会升高，请在该位置用 0 来代替。

示例

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

提示：气温 列表长度的范围是 [1, 30000]。每个气温的值的均为华氏度，都是在 [30, 100] 范围内的整数。

解题思路

肯定是不可以遍历每一个元素，向后扫描找比他大的元素的位置，这样做的时间复杂度为O(n^2)。

给出单调栈的方法：

遍历每日温度，维护一个单调栈。若栈为空或者当日温度小于等于栈顶温度则直接入栈；反之若当日温度大于栈顶温度，说明栈顶元素的升温日已经找到了，则将栈顶元素出栈，计算其与当日相差的天数即可（只要栈顶元素对应的温度小于当日温度就一直重复该操作，直到栈为空或者栈顶元素对应温度大于等于当日温度为止，这时再把当日温度入栈）。注意题目要求的是升温的天数，而不是升温后的温度，因此栈中应该存储下标，而非温度。

public static int[] dailyTemperatures(int[] T) {
    //防御型编程
    if (T==null||T.length==0) return null;
    //没有用ArrayDeque是因为有频繁的入栈出栈操作
    Deque<Integer> stack = new LinkedList<>();
    int[] wait = new int[T.length];
    for (int i = 0; i < T.length; i++) {
        //对于当前的T[i]，只要栈不为空且T[i]大于栈顶对应的日子的气温
        while (!stack.isEmpty() && T[i] > T[stack.peek()]) {
            //计算日期差放入结果数组
            wait[stack.peek()] = i - stack.pop();
        }
        stack.push(i);
    }
    //最后以所有栈中元素i为下标的日子往后没有更高气温的天数
    //wait[i]初始化时为0不用再修改
    return wait;
}

---

类似地，496题下一个更大元素I (opens new window)也可以用单调栈的方式求解，不过这一题由于给的两个数组不等长，且顺序可能不同，需要用一个Map保存值和下标以便在出栈时判断元素是否是目的数组中的元素，并且快速找到其下标。

给定两个 没有重复元素 的数组 nums1 和 nums2 ，其中nums1 是 nums2 的子集。找到 nums1 中每个元素在 nums2 中的下一个比其大的值。 nums1 中数字 x 的下一个更大元素是指 x 在 nums2 中对应位置的右边的第一个比 x 大的元素。如果不存在，对应位置输出 -1 。

示例

输入: nums1 = [4,1,2], nums2 = [1,3,4,2].
输出: [-1,3,-1]
解释:
    对于num1中的数字4，你无法在第二个数组中找到下一个更大的数字，因此输出 -1。
    对于num1中的数字1，第二个数组中数字1右边的下一个较大数字是 3。
    对于num1中的数字2，第二个数组中没有下一个更大的数字，因此输出 -1。

代码

import java.util.*;

public class No496_NextGreaterElementI {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        if (nums1==null) return null;
        if (nums1.length==0) return new int[0];

        Deque<Integer> stack=new LinkedList<>();
        Map<Integer,Integer> hash=new HashMap<>();
        int[] result=new int[nums1.length];
        Arrays.fill(result,-1);

        for (int i=0;i<nums1.length;i++) {
            hash.put(nums1[i],i);
        }

        for (int i = 0; i < nums2.length; i++) {
            while (!stack.isEmpty() && nums2[i] > stack.peek()) {
                int num=stack.pop();
                if (hash.containsKey(num)) {
                    result[hash.get(num)]=nums2[i];
                }
            }
            stack.push(nums2[i]);
        }

        return result;
    }
}