D50|单调栈

739.每日温度

初始思路:

暴力解法但是会超时。

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int[] answer = new int[temperatures.length];
        for(int i = 0;i<temperatures.length;i++){
            for(int j = i;j<temperatures.length;j++){
                if(temperatures[j]>temperatures[i]){
                    answer[i] = j-i;
                    break;
                }

            }
        }
        return answer;
    }
}

题解复盘:

首先了解一下单调栈这部分的数据结构

[数据结构]——单调栈-CSDN博客

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

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

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

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

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

即:如果求一个元素右边第一个更大元素,单调栈就是递增的,如果求一个元素右边第一个更小元素,单调栈就是递减的。

 

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int[] answer = new int[temperatures.length];
        Stack<Integer> st= new Stack<>();
        st.push(0);
        for(int i = 1;i<temperatures.length;i++){
            if(temperatures[i]<= temperatures[st.peek()]){
                    st.push(i);
            }else
            {
                while(!st.isEmpty()&&temperatures[i]>temperatures[st.peek()]){

                    answer[st.peek()] = i- st.pop();
                }
                st.push(i);
            }


        }
        return answer;
    }
}

栈内存放的是下标,主要为了记录遍历过的数据,且为了后续方便求下标的距离,如果当前数组元素大于栈顶元素的话,表示该元素是数组内下标元素的最右边第一个最大的值,所以在answer中存放结果,并且pop()栈顶元素,这个过程一直循环到小于栈顶元素,然后就将该元素push进去。


496.下一个更大元素 I

初始思路:

        初始化一个answer数组,answer数组的大小和nums1相同,我觉得都初始化为-1就很好.

        然后当nums2中的元素等于nums1的元素时,存入栈,如果后面nums2的元素大于栈顶元素就把结果存入answer。

class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
int[] answer = new int[nums1.length];
        Stack<Integer> st = new Stack<>();
        Arrays.fill(answer,-1);
        for(int i = 0;i<nums1.length;i++){
            for(int j= 0;j<nums2.length;j++){
                if(j==0&&!st.isEmpty()){st.pop();}
                if(nums2[j]==nums1[i]){
                    st.push(nums2[j]);
                    System.out.println(st.peek());
                }
                else if(!st.isEmpty()&&nums2[j]>st.peek()){
                    System.out.println("j"+nums2[j]);
                    System.out.println("stpeek"+st.peek());
                        answer[i] = nums2[j];
                        st.pop();
                }

            }
        }
        return answer;
        
    }
}

没太感觉出来单调栈用在哪里了。

题解复盘: 

1.用map来做映射:

unordered_map<int, int> umap; // key:下标元素,value:下标
for (int i = 0; i < nums1.size(); i++) {
    umap[nums1[i]] = i;
}
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;
    }
}

 意思就是在nums2中做单调栈任务,然后再将该元素映射回nums1中寻找其在nums1中的角标(HashMap),再填写在结果数组中。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/292287.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

C# 2中的一些小特性

一、局部类型 在C#当中有这样一个关键字partial 用来声明类&#xff0c;结构&#xff0c;接口分为多个部分来声明。使用场景可以一部分类中写实例方法&#xff0c;一部分写属性&#xff0c;我在实际工作测试中就是将属性与实际方法是分开的。相互之间的成员互相通用。 举个例子…

C# 反射的终点:Type,MethodInfo,PropertyInfo,ParameterInfo,Summry

文章目录 前言反射是什么&#xff1f;常用类型操作SummryPropertyInfoMethodInfo无参函数运行 有参函数运行,获取paramterInfo 总结 前言 我之前写了一篇Attribute特性的介绍&#xff0c;成功拿到了Attribute的属性&#xff0c;但是如果把Attribute玩的溜&#xff0c;那就要彻…

关键字:instanceof关键字

在 Java 中&#xff0c;instanceof关键字用于检查一个对象是否是某个特定类或其子类的实例。它的语法如下&#xff1a; 其中&#xff0c;Object是要检查的对象&#xff0c;Class是要检查的类或接口。 instanceof关键字的返回值是一个布尔值&#xff0c;如果对象Object是类Cla…

基于Spring Boot的美妆分享系统:打造个性化推荐、互动社区与智能决策

基于Spring Boot的美妆分享系统&#xff1a;打造个性化推荐、互动社区与智能决策 1. 项目介绍2. 管理员功能2.1 美妆管理2.2 页面管理2.3 链接管理2.4 评论管理2.5 用户管理2.6 公告管理 3. 用户功能3.1 登录注册3.2 分享商品3.3 问答3.4 我的分享3.5 我的收藏夹 4. 创新点4.1 …

【UWB定位源码】工厂企业人员定位系统源码,实现安全区域管控、人员在岗监控、车辆实时轨迹监控

UWB高精度定位系统源码&#xff0c;企业工厂人员定位系统源码 概念&#xff1a; UWB (ULTRA WIDE BAND, UWB) 技术是一种无线载波通讯技术&#xff0c;它不采用正弦载波&#xff0c;而是利用纳秒级的非正弦波窄脉冲传输数据&#xff0c;因此其所占的频谱范围很宽。 UWB的主要特…

2023-RunwayML-Gen-2 AI视频生成功能发展历程

RunwayML是一个人工智能工具&#xff0c;它为设计师、艺术家和创意人士提供了一种简单的方式来探索和应用机器学习技术。 RunwayML官方网页地址&#xff1a;Runway - Advancing creativity with artificial intelligence. RunwayML专区RunwayML-喜好儿aigcRunwayML 是一种先进…

Java ArrayList 面试题

Java ArrayList 面试题 文章目录 Java ArrayList 面试题ArrayList源码分析成员变量构造方法ArrayList源码分析面试题-ArrayList listnew ArrayList(10)中的list扩容几次面试题-如何实现数组和List之间的转换 ArrayList源码分析 分析ArrayList源码主要从三个方面去翻阅&#xf…

MySQL数据库索引优化实战

目录 一、前言 二、准备工作 2.1 用户表&#xff08;TB_USER) 2.2 商品表&#xff08;TB_SKU) 2.3 订单表&#xff08;TB_ORDER&#xff09; 三、实例分析 3.1 索引提升查询性能 3.2 多表查询 3.3 索引失效 四、总结 一、前言 在数据库的应用中&#xff0c;性能优化…

SpringBoot从配置文件中获取属性的方法

方式一&#xff1a;Value 基本类型属性注入&#xff0c;直接在字段上添加Value("\${xxx.xxx}")即可&#xff0e;注意这里用的是$&#xff0c;而不是&#xff03;&#xff0c;Value注入的属性&#xff0c;一般其他属性没有关联关系。 配置文件 user:name: Manaphya…

【搜索引擎】elastic search核心概念

前言 本文不涉及ES的具体安装下载、操作、集群的内容&#xff0c;这部分内容会放在后面一篇文章中。本文只包含ES的核心理论&#xff0c;看完本文再去学ES的细节会事半功倍。 目录 1.由日志存储引出的问题 2.什么是ES&#xff1f; 3.ES的数据结构 4.ES的核心原理 5.联系作…

高效工具汇总,让学习和办公飞起来

目录 1、寻找论文&#xff0c;效率很高2、学习各类编程的地方 1、寻找论文&#xff0c;效率很高 AMiner&#xff0c;由清华大学计算机科学与技术系的唐杰教授团队开发的一个显著的学术搜索和挖掘系统。系统提供了一整套功能以协助学术研究&#xff0c;包括研究人员档案、专家搜…

MySQL8.0安装教程

Mysql安装教程 1.Mysql下载 进入官网https://www.mysql.com/进行下载&#xff1a; 2.Mysql安装 双击文件进行安装&#xff0c;选择默认安装方式&#xff1a; 这里列出了五种安装类型&#xff1a; Developer Default&#xff1a;默认安装类型&#xff1b;Server only&#x…

性能测试浅谈

早期的性能测试更关注后端服务的处理能力。 一个用户去访问一个页面的请求过程&#xff0c;如上图。 数据传输时间 当你从浏览器输入网址&#xff0c;敲下回车&#xff0c;开始... 真实的用户场景请不要忽视数据传输时间&#xff0c;想想你给远方的朋友写信&#xff0c;信件需…

java基础之String的不可变性

目录 概述 String是如何实现不可变的 String为何设计成不可变的 1.缓存和性能优化 2.安全性 3.线程安全性 4.API设计和预测性能 概述 String类的不可变性意味着一旦创建了一个字符串对象&#xff0c;它的值就不能被修改。 String是如何实现不可变的 查看源码 public …

Django 6 后台与便签

1. 什么是后台管理 后台管理是网页管理员利用网页的后台程序管理和更新网站上网页的内容。各网站里网页内容更新就是通过网站管理员通过后台管理更新的。 2. 创建超级用户 1. python .\manage.py createsuperuser 2. 输入账号密码等信息 Username (leave blank to use syl…

Gromacs make_ndx建组问题

1. 选择特定分子或原子&#xff1a; gmx make_ndx -f input.gro -o output.ndx这将打开交互式界面&#xff0c;您可以在其中选择要包含在索引文件中的分子和原子。按照提示进行操作&#xff0c;选择适当的分组。 2. 手动创建索引文件&#xff1a; 您还可以手动创建一个文本文件…

佳能G3800彩色喷墨多功能一体打印机报5B00错误代码处理方法

5B00错误代码的含义 5B00错误代码是指佳能G3800打印机的“废墨仓已满”。这个废墨仓是打印机内部的一个部件&#xff0c;主要用于收集打印过程中产生的废墨。当废墨仓已满时&#xff0c;打印机就会报5B00错误代码。 佳能G3800彩色喷墨多功能一体打印机报5B00错误代码处理办法 …

【软件测试】接口自动化测试面试题及详细答案

&#x1f4e2;专注于分享软件测试干货内容&#xff0c;欢迎点赞 &#x1f44d; 收藏 ⭐留言 &#x1f4dd; 如有错误敬请指正&#xff01;&#x1f4e2;交流讨论&#xff1a;欢迎加入我们一起学习&#xff01;&#x1f4e2;资源分享&#xff1a;耗时200小时精选的「软件测试」资…

【每天五道题,轻松公务员】Day3:太阳常识

目录 专栏了解 ☞欢迎订阅☜ ★专栏亮点★ ◇专栏作者◇ 太阳常识 题目一 题目二 题目三 题目四 题目五 答案 补充扩展 专栏了解 ☞欢迎订阅☜ 欢迎订阅此专栏&#xff1a;考公务员&#xff0c;必订&#xff01;https://blog.csdn.net/m0_73787047/category_1254…

ROS 系列学习教程(总目录)

ROSLearning 一、ROS概览 1.1 ROS简介 To be continued… 1.2 ROS安装 Ubuntu 安装 ROS 详细教程&#xff08;以最后一个ROS1版本Noetic为例&#xff09; 1.3 ROS Hello World ROS创建工作空间添加包并编译 ROS Hello World 1.4 ROS架构 ROS架构&#xff1a;文件系统 …