算法训练营day49 | {739.每日温度, 496.下一个更大元素 I, 503.下一个更大元素II}

第10章单调栈-part01，用来解决求下一个比自己大或者小的元素。

0. 单调栈

• 什么时候用单调栈？
  • 在一维数组中，要寻找任一个元素的右边或者左边第一个比自己大或小的元素的位置，此时要想到用单调栈。
• 单调栈的原理？
  • 空间换时间，整个数组只需遍历一次(O(n))就可以找到每一个元素的右边第一个比它大的元素。
• 使用单调栈时要明确：
  1. 单调栈里存放的元素是什么？
     • 只需存放元素对应的下标，如需使用对应的元素，直接T[i]就可以获取。
  2. 单调栈里的元素是递增呢？还是递减呢？（指从栈头到栈底的顺序）
     • 如果求一个元素右边第一个更大元素，单调栈就是递增的，如果求一个元素右边第一个更小元素，单调栈就是递减的。

总结来说，就说用栈的数据结构来模拟一种单调递增、或者单调递减的栈的性质，用于解决找第一个比自己大或者小的元素！

739. 每日温度

• 题目链接：739. 每日温度
• 文档讲解：代码随想录
• 视频讲解：单调栈，你该了解的，这里都讲了！LeetCode:739.每日温度
• 状态：模拟单调栈的数据结构解决第一个比自己更大元素的问题。

1.1 解题分析

索引 i	0	1	2	3	4	5	6	7	8
T	73	74	75	71	69	69	72	76	73
输出	1	1	5	3	2	1	1	0	0

---

• 使用单调栈主要有三个判断条件。
  • 当前遍历的元素T[i]小于栈顶元素T[st.top()]的情况
  • 当前遍历的元素T[i]等于栈顶元素T[st.top()]的情况
  • 当前遍历的元素T[i]大于栈顶元素T[st.top()]的情况

1.2 解题小结

• 解题的时候要注意，单调栈里面存的是数组下标！！

▶

739. 每日温度

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int[] res = new int[temperatures.length];
        Deque<Integer> stack = new ArrayDeque<>();
        stack.offerFirst(0);
        for (int i = 1; i < temperatures.length; i++) {
            if (temperatures[i] <= temperatures[stack.peekFirst()]) {
                stack.offerFirst(i);
            } else {
                while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peekFirst()]) {
                    Integer index = stack.pollFirst();
                    res[index] = i - index;
                }
                stack.offerFirst(i);
            }
        }
        return res;
    }
}

496. 下一个更大元素 I

• 题目链接：496.下一个更大元素 I
• 文档讲解：代码随想录
• 视频讲解：单调栈，套上一个壳子就有点绕了| LeetCode:496.下一个更大元素
• 状态：听了单调栈的解题思路之后做出来了。

2.1 解题分析

注意几个要点:

1. 遍历的是nums2数组，并且单调栈中保存num2元素的下标。
2. 要找右边比自己大的第一个元素，单调栈是一个单调递增的栈。
3. 依据题意，nums1是nums2的子集，要建议两个数组的哈希映射关系，Map<nums2[?], nums1中对应的下标>
4. 结果数组初始化为-1。

2.2 解题小结

▶

496.下一个更大元素 I

class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        int[] res = new int[nums1.length];
        Arrays.fill(res, -1);
        Map<Integer, Integer> occur = new HashMap<>();
        for (int num : nums2) {
            for (int i = 0; i < nums1.length; i++) {
                if (num == nums1[i]) {
                    occur.put(num, i);
                    break;
                }
            }
        }
        Deque<Integer> stack = new ArrayDeque<>();
        stack.offerFirst(0);
        for (int i = 1; i < nums2.length; i++) {
            if (!stack.isEmpty() && nums2[i] <= nums2[stack.peekFirst()]) {
                stack.offerFirst(i);
            } else {
                while (!stack.isEmpty() && nums2[i] > nums2[stack.peekFirst()]) {
                    Integer index = stack.pollFirst();
                    if (occur.containsKey(nums2[index])) {
                        Integer idx = occur.get(nums2[index]);
                        res[idx] = nums2[i];
                    }
                }
                stack.offerFirst(i);
            }
        }
        return res;
    }
}

503. 下一个更大元素II

• 题目链接：503.下一个更大元素II
• 文档讲解：代码随想录
• 视频讲解：单调栈，成环了可怎么办？LeetCode：503.下一个更大元素II
• 状态：模拟循环两遍nums数组，仍然使用单调栈求下一个比自己大的元素。

3.1 解题分析

• 看了代码随想录的题解，和我写法的区别在于用取模来解决第二次循环的数组下标问题，达到统一。

  for (int i = 1; i < nums.size() * 2; i++) { 
      // 模拟遍历两边nums，注意一下都是用i % nums.size()来操作
      if (nums[i % nums.size()] < nums[st.top()]) st.push(i % nums.size());
      else if ()....
  }

3.2 解题小结

▶

503.下一个更大元素II

class Solution {
    public int[] nextGreaterElements(int[] nums) {
        int[] res = new int[nums.length];
        Arrays.fill(res, -1);
        Deque<Integer> stack = new ArrayDeque<>();
        stack.offerFirst(0);
        loopArray(stack, nums, res, 1);
        loopArray(stack, nums, res, 0);
        return res;
    }

    private void loopArray(Deque<Integer> stack, int[] nums, int[] res,int startIndex) {
        for (int i = startIndex; i < nums.length; i++) {
            if (!stack.isEmpty() && nums[i] <= nums[stack.peekFirst()]) {
                stack.offerFirst(i);
            } else {
                while (!stack.isEmpty() && nums[i] > nums[stack.peekFirst()]) {
                    Integer index = stack.pollFirst();
                    res[index] = res[index] == -1 ? nums[i] : res[index];
                }
                stack.offerFirst(i);
            }
        }
    }
}

4. 今日收获

• 比较简单，就是模拟一个单调递增/递减的栈，来解决特定的问题。
• 学习时长：3小时