代码随想录算法训练营第58天 | 392.判断子序列 ， 115.不同的子序列

单调栈章节理论基础：

https://leetcode.cn/problems/daily-temperatures/

739. 每日温度

题目链接：https://leetcode.cn/problems/daily-temperatures/

思路：

首先想到的当然是暴力解法，两层for循环，把至少需要等待的天数就搜出来了。时间复杂度是O(n^2)
如果用单调栈的话，能把时间复杂度降到O(n)。单调栈的本质是空间换时间，因为在遍历的过程中需要用一个栈来记录右边第一个比当前元素高的元素，优点是整个数组只需要遍历一次。

用一个栈来记录我们遍历过的元素，因为我们遍历数组的时候，我们不知道之前都遍历了哪些元素，以至于遍历一个元素找不到是不是之前遍历过一个更小的，所以我们需要用一个容器（这里用单调栈）来记录我们遍历过的元素。

定义的时候，根据题目意思来，如果求一个元素右边第一个更大元素，单调栈就是递增的，如果求一个元素右边第一个更小元素，单调栈就是递减的。

本题使用的是递增栈。使用单调栈主要有三个判断条件。

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

情况1和情况2是一样的，因为我们要找的是第一个大于他的温度，只需要让他入栈保存。
对于情况3，也就意味着找到了第一个大于他的温度，我们需要把res对应的下标，与对应的数值(两个下标的间隔)对应起来。同时，这里是要用while的，因为栈中可能有多个元素都找到解，依次让他们pop保存结果。最后，别忘了把当前的数字入栈。

代码：

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int n = temperatures.length;
        int[] res = new int[n];
        Deque<Integer> stack = new LinkedList<>();
        stack.push(0);
        for(int i=1;i<n;i++){
            if(temperatures[stack.peek()] >= temperatures[i])
                stack.push(i);
            else{
                while(!stack.isEmpty() && temperatures[stack.peek()] < temperatures[i]){
                    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

496.下一个更大元素 I

题目链接：https://leetcode.cn/problems/next-greater-element-i/

思路：

本题则是说nums1 是 nums2的子集，找nums1中的元素在nums2中下一个比当前元素大的元素。需要对单调栈使用的更熟练一些，才能顺利的把本题写出来。

一开始看到两个数组都有点懵了，不知道要定一个一个多大的result数组来存放结果了。**注意题目中说是两个没有重复元素 的数组 nums1 和 nums2。**没有重复元素，我们就可以用map来做映射了。根据数值快速找到下标，还可以判断nums2[i]是否在nums1中出现过。（关键！）

本题和739. 每日温度是一样的。栈头到栈底的顺序，要从小到大，也就是保持栈里的元素为递增顺序。只要保持递增，才能找到右边第一个比自己大的元素。

同时初始化的时候，题目说如果不存在对应位置就输出 -1 ，所以result数组如果某位置没有被赋值，那么就应该是是-1，所以就初始化为-1。其他的和上一题就大同小异了，就是还需要加个判断map中是否包含nums1中的元素。map初始化的时候，value设置成当前的下标就行了。

代码：

class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        // 用hashMap做num1 - nums2的映射
        int n1 = nums1.length;
        int n2 = nums2.length;
        HashMap<Integer,Integer>map = new HashMap<>();
        for(int i=0;i<n1;i++){
            map.put(nums1[i],i);
        }
        Stack<Integer>stack = new Stack<>();
        int[] res = new int[n1];
        Arrays.fill(res,-1);
        stack.push(0);
        for(int i=1;i<n2;i++){
            if(nums2[stack.peek()] >= nums2[i])
                stack.push(i);
            else{
                while(!stack.isEmpty() && nums2[stack.peek()] < nums2[i]){
                    if(map.containsKey(nums2[stack.peek()])){
                        // 这道题不是找下标，是找元素了
                        res[map.get(nums2[stack.peek()])] = 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