算法训练营（day58）

单调栈原理

单调栈的本质是空间换时间，因为在遍历的过程中需要用一个栈来记录右边第一个比当前元素高的元素，优点是只需要遍历一次。

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

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

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

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

注意一下顺序为 从栈头到栈底的顺序，这里我们要使用递增循序（再强调一下是指从栈头到栈底的顺序），因为只有递增的时候，加入一个元素i，才知道栈顶元素在数组中右面第一个比栈顶元素大的元素是i。

单调栈判断条件

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

739. 每日温度

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

给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。

解题思路

解题过程：

  1. 解题的关键在于：保证栈顶的元素是之前遍历的 最大值
  2. 定义一个 栈 ，用于存放 数组下标
  3. 遍历整个整数数组temperatures，添加单调栈判断条件：
    • 当前遍历的元素T[i]小于等于栈顶元素T[st.top()]的情况，直接压栈
    • 当前遍历的元素T[i]大于栈顶元素T[st.top()]的情况，answer[i]记录，并将已记录的元素从栈中弹出
  4. 返回 ans

详细代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int len = temperatures.length;
        int[] res = new int[len];
        Deque<Integer> stack = new LinkedList<>();

        for(int i = 0; i < len; i++){
            while(!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]){
                res[stack.peek()] = i - stack.peek();
                stack.pop();
            }
            stack.push(i);
        }
        return res;
    }
}

496. 下一个更大元素 I

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

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. 解题的关键在于：保证栈顶的元素是之前遍历的 最大值
  2. 定义一个map，用于对应 nums1 的元素和下标
  3. 定义一个 栈 ，用于存放 数组下标
  4. 遍历整个数组nums2，添加单调栈判断条件：
    • 当前遍历的元素 nums2[i] 小于等于栈顶元素 nums2[stack.peek()] 的情况，直接压栈
    • 当前遍历的元素 nums2[i] 大于栈顶元素 nums2[stack.peek()] 的情况，将栈顶元素弹出，记录 nums2[stack.pop()]的值，在map中找 nums1是否有符合的元素，如果有，记录进 res[map.get(stack.pop())]中
  5. 返回 res

详细代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        int[] res = new int[nums1.length];
        Arrays.fill(res, -1);
        HashMap<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i < nums1.length; i++){
            map.put(nums1[i], i);
        }
        
        Stack<Integer> stack = new Stack<>();
        for(int i = 0; i < nums2.length; i++){
            while(!stack.isEmpty() && nums2[stack.peek()] < nums2[i]){
                int pop = nums2[stack.pop()];
                if(map.containsKey(pop)){
                    res[map.get(pop)] = nums2[i];
                }
            }
            stack.push(i);
        }
        return res;
    }
}

503. 下一个更大元素 II

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

给定一个循环数组 nums （ nums[nums.length - 1] 的下一个元素是 nums[0] ），返回 nums 中每个元素的 下一个更大元素 。

数字 x 的 下一个更大的元素 是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1 。

解题思路

解题过程：

  1. 解题的关键在于：保证栈顶的元素是之前遍历的 最大值
  2. 本题相较 上一题，增加了一个 循环遍历数组的要求，实现起来只需 将数组复制多一份即可，循环遍历时，取下标的余数即可实现循环遍历
  3. 定义一个 栈 ，用于存放 数组下标
  4. 遍历整个数组nums2，添加单调栈判断条件：
    • 当前遍历的元素 nums[i % len] 小于等于栈顶元素 nums[stack.peek()] 的情况，直接压栈
    • 当前遍历的元素 nums[i % len] 大于栈顶元素 nums[stack.peek()] 的情况，将栈顶元素弹出，将 nums[i % len] 记录进 res[stack.peek()]中
  5. 返回 res

详细代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int[] nextGreaterElements(int[] nums) {
        if(nums == null || nums.length <= 1){
            return new int[]{-1};
        }

        int len = nums.length;
        Stack<Integer> stack = new Stack<>();
        int[] res = new int[len];
        Arrays.fill(res, -1);

        for(int i = 0; i < 2 * len; i++){
            while(!stack.isEmpty() && nums[i % len] > nums[stack.peek()]){
                res[stack.peek()] = nums[i % len];
                stack.pop();
            }
            stack.push(i % len);
        }
        return res;
    }
}