代码随想录算法训练营第六十天 | 739. 每日温度 & 496.下一个更大元素 I

1. 每日温度

维护一个单调递减（可以等于）的栈，栈内存的是元素的下标

当前元素小于等于栈顶元素时，直接入栈

否则，将栈顶元素出栈（对于栈顶元素，它找到了它的答案，即下标之差）

循环比较记录结果，直到当前元素入栈后，栈依然单调递减


class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int length = temperatures.length;
        int[] res = new int[length];
        Stack stack = new Stack<>();
        stack.push(0);
        for(int i = 1; i < length; 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. 下一个更大元素 I

496. 下一个更大元素 I - 力扣（LeetCode）

和前面差不多，只不过需要返回的结果要处理下


class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        Map map = new HashMap<>();
        for(int i = 0; i < nums1.length; i++){
            map.put(nums1[i], i);
        }
 
        Stack stack = new Stack<>();
        stack.push(nums2[0]);
        int[] res = new int[nums1.length];
        Arrays.fill(res, -1);
        for(int i = 0; i < nums2.length; i++){
            if(nums2[i] <= stack.peek()){
                stack.push(nums2[i]);
            }else{
                while(!stack.isEmpty() && nums2[i] > stack.peek()){
                    if(map.containsKey(stack.peek())){ // 只有当栈顶元素需要被记录时才记录
                        int idx = map.get(stack.peek()); // 取出记录该在的位置
                        res[idx] = nums2[i];
                    }
                    stack.pop(); // 不需要记录的元素也需要出栈，继续看前一个元素
                }
                stack.push(nums2[i]);
            }
        }
 
        return res;
    }
}

相关阅读:
【亲妈教学】配置Gzip压缩，含前后端步骤
70.【JavaScript 6.0】
实现字符串反转函数
实习打怪之路：ES6中的Sym详解
企业一般纳税人查询API：简化税务信息获取的利器
【云原生丨Docker系列7】Docker的四种网络模式详解
【计网】计算机网络学习笔记目录
【软件设计师】多元化多方面了解多媒体技术的内容
网络面试-0x03http有哪些常见的请求头以及作用
Linux文件系统 struct file 结构体解析

原文地址：https://blog.csdn.net/weixin_50815909/article/details/133631324