Day49 力扣单调栈 : 739. 每日温度 ｜496.下一个更大元素 I

739. 每日温度

今天正式开始单调栈，这是单调栈一篇扫盲题目，也是经典题。

大家可以读题，思考暴力的解法，然后在看单调栈的解法。 就能感受出单调栈的巧妙

https://programmercarl.com/0739.%E6%AF%8F%E6%97%A5%E6%B8%A9%E5%BA%A6.html

第一印象

暴力解法还是比较好想的

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int[] answer = new int[temperatures.length];

        for (int i = 0; i < answer.length; i++) {
            int curTemp = temperatures[i];
            int day = 1;
            //flag 0代表没有更高的那天，1代表有更高的那天
            int flag = 0;
            for (int j = i + 1; j < temperatures.length; j++) {
                if (temperatures[j] > curTemp) {
                    answer[i] = day;
                    flag = 1;
                    break;
                } else {
                    day++;
                }
            }
            if (flag == 0) answer[i] = 0;
        }
        return answer;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

当然，直接超时了，下面学习单调栈。

看完题解的思路

我看完单调栈的工作过程了, 太tm神奇了.

什么是单调栈?

单调栈就是用于找一个元素左 / 右第一个比自己大 / 小的元素的题目。

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

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

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

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

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

注意以下讲解中，顺序的描述为 从栈头到栈底的顺序，因为单纯的说从左到右或者从前到后，不说栈头朝哪个方向的话，大家一定比较懵。

这道题我们要让栈里的元素是递增的 (从栈头到栈底)

对于数组我们从左到右遍历, 每次拿来的元素 i 都是遍历过的元素的右面的. 这就实现了找右面更大 / 更小的元素.

而栈里, 我们让元素都是递增的. 这样每次拿来元素 i ,就是 栈顶元素右侧第一个比栈顶元素大的. 这里会产生一个疑问: 比如栈里是 69 71. 71 不是比栈顶元素 69 大吗?

是的, 但 71 是 69 左侧的元素. 因为数组遍历顺序是从左到右, 然后压入栈. 所以越靠近栈头的元素在数组里越靠右, 栈尾则靠左.

那如果拿来的元素 i 比栈顶元素更小呢? 那压入栈就可以了. 栈递增所以栈顶元素就是栈里最小的, 拿到的元素 i 比最小的还要小, 所以不会比栈内任何元素大, 就说明还没找到这些元素右侧第一个更大的.

我的总结

所以求右侧第一个更大元素时, 为什么让栈内元素递增?

因为栈内元素递增, 栈头元素就是最小的那个. 因为数组从左到右遍历, 栈头元素是右侧的, 栈底元素是左侧的.

每次拿来元素 i 和栈头元素比较, 没有栈头大就没有任何栈内元素大, 就压入栈.

元素 i 比栈头元素大, 就找到了栈头元素右侧第一个更大. 记录结果, 弹出栈头元素. 当然也要用元素 i 继续和新栈头元素比较, 直到元素 i 比新栈头元素小而压入栈, 或者栈空了元素 i 就压入栈.

那么如果找右侧第一个更小, 就应该让栈内元素递减了.

每次其实只有三种操作:

• 元素 i 比栈头元素大
• 元素 i 比栈头元素小
• 元素 i 和栈头元素相等

只要分别写出三中操作的代码, 就写完这道题了. 用这三种操作控制栈内元素是递增的, 就可以了.

实现中的苦难

思路清晰没有困难

int index = stack.pop();
answer[index] = i - index;
1
2

记录结果的时候要注意别岔劈了.

感悟

具体的图解模拟过程, 到代码随想录里看一下吧.

第一次看完视频感觉单调栈很神奇, 甚至有点不知道为什么会产生这种效果.

我觉得多做做题就理解了, 而且这个也挺套路的.

代码

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int[] answer = new int[temperatures.length];

        //声明单调栈  空间换时间
        Deque<Integer> stack=new LinkedList<>();

        //先把第一个元素加入栈里
        stack.push(0);

        for (int i = 1; i < temperatures.length; i++) {
            //元素 i 比栈顶元素小 或相等 都应该压入
            if (temperatures[i] <= temperatures[stack.peek()]) {
                stack.push(i);
            } else {
                //如果元素i比栈顶元素大,就要记录结果并弹出栈顶, 继续比较,直到没有栈顶元素大
                while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
                    int index = stack.pop();
                    answer[index] = i - index;
                }
                stack.push(i);
            }
        }

        return answer;
    }
}
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

496.下一个更大元素 I

本题和 739. 每日温度 看似差不多，其实 有加了点难度。

https://programmercarl.com/0496.%E4%B8%8B%E4%B8%80%E4%B8%AA%E6%9B%B4%E5%A4%A7%E5%85%83%E7%B4%A0I.html

第一印象

试了试,我有点迷糊.

看题解吧, 我真绕进去了.

我写的 num1 的元素 在 num2 中的位置是这么写的, 但卡哥说要用 map.

for (int i = 0; i < nums1.length; i++) {
    //num1里当前的元素
    int cur = nums1[i];
    int indexInNum2 = -1;
    //找到当前元素在num2里的下标
    for (int j = 0; j < nums2.length; j++) {
        if (nums2[j] == cur) {
            indexInNum2 = j;
        }
    }
   
}
1
2
3
4
5
6
7
8
9
10
11
12

看完题解的思路

先用 map 记录 num1 中元素的值和下标,值为Key,下标为value

这样我们就可以只对 num2 做经典的单调栈操作, 如果我要pop的那个下标在map里, 就要记录结果.

 //如果拿来的元素 i 比栈顶元素更大, 持续比较
 while (!stack.isEmpty() && nums2[i] > nums2[stack.peek()]) {
     int index = stack.pop();
     int cur = nums2[index];
     //如果弹出的元素是在map里的(nums1里的),就要记录结果
     //如果不是nums1里的,只弹出就可以了
     if (map.containsKey(cur)) {
         //res[在nums1里的下标] = 下一个更大的数值.
         res[map.get(cur)] = nums2[i];
     }
 }
 //拿来的元素 i 在比较之后, 一定要push进栈.
 stack.push(i);
1
2
3
4
5
6
7
8
9
10
11
12
13

就是比较绕, 一会是下标, 一会是元素.

每日温度是, 对于 每一个找到了更大的元素都 pop并记录结果到result里.

这道题是, 对于每一个找到了更大的元素都pop, 但只有在nums1(在map)里的才记录到结果result里.

实现中的困难

没有

感悟

用map来不被绕进去, 解决单调栈套的这个壳子.

还是实现能力不够啊

代码

class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        HashMap<Integer, Integer> map = new HashMap<>();
        //num1中值为Key, 下标为Value
        for (int i = 0; i < nums1.length; i++) {
            map.put(nums1[i], i);
        }

        int[] res = new int[nums1.length];
        Deque<Integer> stack = new LinkedList<>();
        //先都初始化为 -1.
        Arrays.fill(res, -1);

        stack.push(0);
        for (int i = 1; i < nums2.length; i++) {
            if (nums2[i] <= nums2[stack.peek()]) {
                stack.push(i);
            } else {
                //如果拿来的元素 i 比栈顶元素更大, 持续比较
                while (!stack.isEmpty() && nums2[i] > nums2[stack.peek()]) {
                    int index = stack.pop();
                    int cur = nums2[index];
                    //如果弹出的元素是在map里的(nums1里的),就要记录结果
                    //如果不是nums1里的,只弹出就可以了
                    if (map.containsKey(cur)) {
                        //res[在nums1里的下标] = 下一个更大的数值.
                        res[map.get(cur)] = nums2[i];
                    }
                }
                //拿来的元素 i 在比较之后, 一定要push进栈.
                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
33
34
35
36