LeetCode算法题解（单调栈）|LeetCode739. 每日温度、LeetCode496. 下一个更大元素 I

一、LeetCode739. 每日温度

题目链接：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]

示例 2:

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

示例 3:

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

提示：

• 1 <=?temperatures.length <= 105
• 30 <=?temperatures[i]?<= 100

算法分析：

创建一张单调栈用来存放在遍历数组时还没出现下一个递增数的元素下标。

在遍历数组时如果出现递增的元素temperatures[i]，也就是比下标为栈顶的元素大的数，那么将栈顶弹出，同时标记下标为弹出元素的数组元素的下一个更大值是当前元素temperatures[i]，然后再比较下一个栈顶元素，直到到下标为栈顶元素的数组元素大于等于当前元素temperatures[i]时，将当前元素的下标i压入栈当中，表示第i个元素还没出现下一个更大的元素。

代码如下：

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        int len = temperatures.size();
        vector<int>answer(len);
        deque<int> que;//用来存放单调递减的元素的下标
        for(int i = 0; i < len; i++) {
            while(!que.empty() && temperatures[que.back()] < temperatures[i]){//如果出现递增的元素，将栈顶元素弹出，栈顶元素代表数组元素的下标，也就是说下标为栈顶元素的数组元素，下一个更大的数是下标为i的数组元素，记录下来，然后再判断是否弹出下一个栈顶元素。
                int index = que.back();
                que.pop_back();
                answer[index] = i - index;
            }
            que.push_back(i);
        }
        return answer;
        
    }
};

二、LeetCode496. 下一个更大元素 I

题目链接：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 。

示例 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 <= nums1.length <= nums2.length <= 1000
• 0 <= nums1[i], nums2[i] <= 104
• nums1和nums2中所有整数?互不相同
• nums1?中的所有整数同样出现在?nums2?中

算法分析：

先创建一张map哈希表来存放nums1中的元素及其下标，代表nums2中出现过的nums1元素和该元素在nums1中的下标位置。

然后创建一张单调栈用来记录nums2中还没出现过下一个更大元素的元素下标。

然后遍历数组nums2，如果栈为空或者当前的元素nums2[i]小于等于以栈顶元素为标的nums2数组元素，表示以栈内的元素为下标的nums2数组元素还没出现下一个更大的元素，将当前元素的下标i压入栈中。此时当前元素是以栈内元素为下标的数组元素中最小的元素。

如果当前的元素大于以栈顶元素为下标的数组元素，那么该数组元素的下一个更大的元素就是当前元素nums2[i]。将栈顶元素弹出，同时用哈希表map判断以弹出的栈顶元素为下标的数组元素是否在nums1中出现过，如果出现过，就需要将该元素的下一个更大的元素记录下来，也就是当前元素nums2[i]。然后继续判断下一个栈顶元素，直到以栈顶元素为下标的数组元素大于等于当前元素nums[i]时，将当前元素的下标i压入栈中（当前元素的下一个更大元素还没出现）。

最后返回每一个nums1元素在nums2中的下一个更大元素。

代码如下：

class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        int len1 = nums1.length;
        int len2 = nums2.length;
        int[] answer = new int[len1];//用来记录nums1中每个元素的下一个更大元素
        
        Deque<Integer> que = new LinkedList<>();
        HashMap<Integer,Integer>map = new HashMap<>();
        for(int i = 0; i < len1; i++) {
            answer[i] = -1;//用-1初始化nums1中每个元素出现的下一个更大的元素。
            map.put(nums1[i],i);//记录nums1中的元素和下标，表示nums2中出现在nums1的元素和其在nums1中的下标位置
        }
        
        for(int i = 0; i < len2; i++) {
            if(que.isEmpty() || nums2[que.getLast()] >= nums2[i]){//如果栈为空或这当前元素小于等于以栈顶元素为下标的nums2数组元素，将当前元素的下标i压入栈中，此时当前元素是以栈内元素为下标的所有数组元素中最小的元素。
                que.addLast(i);
            }else{
                while(!que.isEmpty() && nums2[que.getLast()] < nums2[i]){//如果当前元素大于以栈顶元素为下标的数组元素
                    int index = que.removeLast();//弹出栈顶元素
                    if(map.containsKey(nums2[index])){//如果以弹出的元素为下标的nums2数组元素在nums1中出现过，那么标记下该元素出现的下一个更大元素，也就是当前元素怒nums2[i]
                        answer[map.get(nums2[index])] = nums2[i];
                    }
                }
                que.addLast(i);//将当前元素的下标压入栈中（当前元素还没出现过下一个更大的元素）
            }
        }
        return answer;

    }
}

总结

单调栈，用来记录数组中还没出现下一递增（或递减的元素）元素的下标，以便在出现递增（或递减）的元素时依次处理这些元素。