代码随想录算法训练营第五十九天|单调栈开始——739. 每日温度 496.下一个更大元素 I 503.下一个更大元素II

单调栈开始

一、739. 每日温度

题目

请根据每日气温列表重新生成一个列表。对应位置的输出为要想观测到更高的气温至少需要等待的天数。如果气温在这之后都不会升高请在该位置用 0 来代替。

例如给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。

提示气温 列表长度的范围是 [1, 30000]。每个气温的值的均为华氏度都是在 [30, 100] 范围内的整数。

思路

首先想到的当然是暴力解法两层for循环把至少需要等待的天数就搜出来了。时间复杂度是O(n^2)。

通常是一维数组要寻找任一个元素的右边或者左边第一个比自己大或者小的元素的位置此时我们就要想到可以用单调栈了。

时间复杂度为O(n)。

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

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

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

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

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

注意一下顺序为 从栈头到栈底的顺序。

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

使用单调栈主要有三个判断条件。

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

class Solution {
  // 版本 1     
    public int[] dailyTemperatures(int[] temperatures) {
        
        int lens=temperatures.length;
        int []res=new int[lens];
        
        /**
        如果当前遍历的元素 大于栈顶元素表示 栈顶元素的 右边的最大的元素就是 当前遍历的元素
        	所以弹出 栈顶元素并记录 
        	如果栈不空的话还要考虑新的栈顶与当前元素的大小关系 
        否则的话可以直接入栈。
        注意单调栈里 加入的元素是 下标。
        */
        Deque<Integer> stack=new LinkedList<>();
        stack.push(0);
        for(int i=1;i<lens;i++){
            
            if(temperatures[i]<=temperatures[stack.peek()]){
                stack.push(i);
            }else{
                while(!stack.isEmpty()&&temperatures[i]>temperatures[stack.peek()]){
                    res[stack.peek()]=i-stack.peek();
                    stack.pop();
                }
                stack.push(i);
            }
        }

        return  res;
    }
    
    //--------这是一条分界线
    // 版本 2 
    class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int lens=temperatures.length;
        int []res=new int[lens];
        Deque<Integer> stack=new LinkedList<>();
        for(int i=0;i<lens;i++){
            
           while(!stack.isEmpty()&&temperatures[i]>temperatures[stack.peek()]){
                    res[stack.peek()]=i-stack.peek();
                    stack.pop();
                }
                stack.push(i);
        }

        return  res;
    }
}
    
}

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

题目

给你两个 没有重复元素 的数组 nums1 和 nums2 其中nums1 是 nums2 的子集。

请你找出 nums1 中每个元素在 nums2 中的下一个比其大的值。

nums1 中数字 x 的下一个更大元素是指 x 在 nums2 中对应位置的右边的第一个比 x 大的元素。如果不存在对应位置输出 -1 。

示例 1:

输入: nums1 = [4,1,2], nums2 = [1,3,4,2].
输出: [-1,3,-1]
解释:
对于 num1 中的数字 4 你无法在第二个数组中找到下一个更大的数字因此输出 -1 。
对于 num1 中的数字 1 第二个数组中数字1右边的下一个较大数字是 3 。
对于 num1 中的数字 2 第二个数组中没有下一个更大的数字因此输出 -1 。

示例 2:
输入: nums1 = [2,4], nums2 = [1,2,3,4].
输出: [3,-1]
解释:
对于 num1 中的数字 2 第二个数组中的下一个较大数字是 3 。
对于 num1 中的数字 4 第二个数组中没有下一个更大的数字因此输出-1 。

提示

• 1 <= nums1.length <= nums2.length <= 1000
• 0 <= nums1[i], nums2[i] <= 10^4
• nums1和nums2中所有整数 互不相同
• nums1 中的所有整数同样出现在 nums2 中

思路

使用单调栈首先要想单调栈是从大到小还是从小到大。

本题和上面那道题是一样的。

栈头到栈底的顺序要从小到大也就是保持栈里的元素为递增顺序。只要保持递增才能找到右边第一个比自己大的元素。

接下来就要分析如下三种情况一定要分析清楚。

1、情况一当前遍历的元素T[i]小于栈顶元素T[st.top()]的情况

此时满足递增栈栈头到栈底的顺序所以直接入栈。

2、情况二当前遍历的元素T[i]等于栈顶元素T[st.top()]的情况

如果相等的话依然直接入栈因为我们要求的是右边第一个比自己大的元素而不是大于等于

3、情况三当前遍历的元素T[i]大于栈顶元素T[st.top()]的情况

此时如果入栈就不满足递增栈了这也是找到右边第一个比自己大的元素的时候。

判断栈顶元素是否在nums1里出现过注意栈里的元素是nums2的元素如果出现过开始记录结果。

HashMap基础Java HashMap | 菜鸟教程

class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        Stack<Integer> temp = new Stack<>();
        int[] res = new int[nums1.length];
        Arrays.fill(res,-1);
        HashMap<Integer, Integer> hashMap = new HashMap<>();
        for (int i = 0 ; i< nums1.length ; i++){
            hashMap.put(nums1[i],i);
        }
        temp.add(0);
        for (int i = 1; i < nums2.length; i++) {
            if (nums2[i] <= nums2[temp.peek()]) {
                temp.add(i);
            } else {
                while (!temp.isEmpty() && nums2[temp.peek()] < nums2[i]) {
                    if (hashMap.containsKey(nums2[temp.peek()])){
                        Integer index = hashMap.get(nums2[temp.peek()]);
                        res[index] = nums2[i];
                    }
                    temp.pop();
                }
                temp.add(i);
            }
        }

        return res;
    }
}

// 版本2
class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums1.length; i++) {
            map.put(nums1[i], i);
        }

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

        for (int i = 0; i < nums2.length; i++) {
            while (!stack.isEmpty() && nums2[stack.peek()] < nums2[i]) {
                int pre = nums2[stack.pop()];
                if (map.containsKey(pre)) {
                    res[map.get(pre)] = nums2[i];
                }
            }
            stack.push(i);
        }

        return res;
    }
}

三、503.下一个更大元素II

题目

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

示例 1:

• 输入: [1,2,1]
• 输出: [2,-1,2]
• 解释: 第一个 1 的下一个更大的数是 2数字 2 找不到下一个更大的数第二个 1 的下一个最大的数需要循环搜索结果也是 2。

思路

不同于每日温度那道题的是本题要循环数组了。

第一想法是两个nums数组拼接在一起使用单调栈计算出每一个元素的下一个最大值最后再把结果集即result数组resize到原数组大小就可以了。

这种写法确实比较直观但做了很多无用操作例如修改了nums数组而且最后还要把result数组resize回去。

resize倒是不费时间是O(1)的操作但扩充nums数组相当于多了一个O(n)的操作。

其实也可以不扩充nums而是在遍历的过程中模拟走了两边nums。

class Solution {
    public int[] nextGreaterElements(int[] nums) {
        //边界判断
        if(nums == null || nums.length <= 1) {
            return new int[]{-1};
        }
        int size = nums.length;
        int[] result = new int[size];//存放结果
        Arrays.fill(result,-1);//默认全部初始化为-1
        Stack<Integer> st= new Stack<>();//栈中存放的是nums中的元素下标
        for(int i = 0; i < 2*size; i++) {
            while(!st.empty() && nums[i % size] > nums[st.peek()]) {
                result[st.peek()] = nums[i % size];//更新result
                st.pop();//弹出栈顶
            }
            st.push(i % size);
        }
        return result;
    }
}