Java算法真题详解运用单调栈

目录
  • 1.下一个更大元素
    • 题目描述
    • 思路详解
    • 代码与结果
  • 2.每日温度
    • 题目描述
    • 思路详解
    • 代码与结果
  • 3.下一个更大元素II
    • 题目描述
    • 思路详解
    • 代码与结果

1.下一个更大元素

题目描述

思路详解

这一题就选取比较暴力 的解法了。

我们先初始化一个与nums等长度的res数组用来存储结果，我们遍历取出nums中的值，到nums2中寻找，直到找到nums2[j] == nums[i] ,我们再从 nums2的 j 之后遍历找到比nums[i]大的数组返回，找不到就返回-1.

代码与结果

class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        int m = nums1.length, n = nums2.length;
        int[] res = new int[m];
        for (int i = 0; i < m; ++i) {
            int j = 0;
            while (j < n && nums2[j] != nums1[i]) {
                ++j;
            }
            int k = j + 1;
            while (k < n && nums2[k] < nums2[j]) {
                ++k;
            }
            res[i] = k < n ? nums2[k] : -1;
        }
        return res;
    }
}

2.每日温度

题目描述

思路详解

这一题也是使用比较暴力的方法。同上一题一样。

两重循环，显然这种方法时间复杂度较高。这里也提供一种时间复杂度较低的方法。

单调栈

我们维护的是一个差距数组也就是结果数组，首先创建一个栈，判断栈是否为空，若为空直接入栈，若不为空则比较栈顶元素与当前元素，如果当前元素大于当前元素就把差值放入到对应结果数组同时栈顶元素出栈，若当前元素小于结果数组则入栈。

这里给一个动画链接很好董，动画学单调栈。

代码与结果

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

3.下一个更大元素II

题目描述

思路详解

本题的思路呢单调栈，问题一暴力破解，这个题要使用单调栈了。

原理同第二题的方法一样，就在循环上注意一下就可以了。直接上代码，不董的可以看第二题的视频再来看这个哦。

代码与结果

class Solution {
    public int[] nextGreaterElements(int[] nums) {
        int n = nums.length;
        int[] ret = new int[n];
        Arrays.fill(ret, -1);
        Deque<Integer> stack = new LinkedList<Integer>();
        for (int i = 0; i < n * 2 - 1; i++) {//最多循环一次，只需要2*n-1就够用了
            while (!stack.isEmpty() && nums[stack.peek()] < nums[i % n]) {
                ret[stack.pop()] = nums[i % n];
            }
            stack.push(i % n);//利用取模来进行循环也是一种常用的方法
        }
        return ret;
    }
}

到此这篇关于Java算法真题详解运用单调栈 的文章就介绍到这了,更多相关Java单调栈 内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • Java数据结构之栈与队列实例详解

    Java数据结构之栈与队列实例详解

    目录 一,栈 1,概念 2,栈的操作 3,栈的实现  4,实现mystack 二,队列 1,概念  2,队列的实现  3,实现myqueue 栈.队列与数组的区别? 总结 一,栈 1,概念 在我们软件应用 ,栈这种后进先出数据结构的应用是非常普遍的.比如你用浏 览器上网时不管什么浏览器都有 个"后退"键,你点击后可以接访问顺序的逆序加载浏览过的网页.   很多类似的软件,比如 Word Photoshop 等文档或图像编 软件中 都有撤销 )的操作,也是用栈这种方式来实现的,当然不同的

  • java数据结构关于栈的实例应用

    java数据结构关于栈的实例应用

    此文章介绍关于顺序栈,链式栈的实例操作,括号匹配,表达式求值(后缀表达式) 1.声明一个栈接口SStack package ch05; public interface SStack <T>{ boolean isEmpty(); // 判断栈是否为空 void push(T x); // 元素x入栈 T pop(); // 出栈,返回栈顶元素 T peek(); // 返回栈顶元素,但不出栈 }  2. 定义顺序栈类SeqStack<T>,包括数据元素的对象数组和栈顶元素下标两个

  • Java栈和基础队列的实现详解

    Java栈和基础队列的实现详解

    目录 栈(stack) 栈支持的三个核心操作: 栈的常见实际应用: 栈的实现 队列 无论是哪种队列,都必须支持三个核心操作: 基础队列的实现 栈和队列:都是线性表,都是基于List基础上的实现 线性表:数组,链表,字符串,栈,队列 元素按照一条“直线”排列,线性表这个结构中,一次添加单个元素 栈(stack) 一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作.进行数据插入和删除操作的一端称为栈顶,另一端称为栈底.栈中的数据元素遵守后进先出LIFO(Last In First Out)

  • Java 栈和队列的相互转换详解

    Java 栈和队列的相互转换详解

    目录 用栈实现队列-力扣232题 用队列实现栈-力扣225题  1. 双队列实现栈 2.一个队列实现栈 栈和队列的本质是相同的,都只能在线性表的一端进行插入和删除.因此,栈和队列可以相互转换. 用栈实现队列-力扣232题 题目要求:仅使用两个栈实现先入先出队列.队列应当支持一般队列支持的所有操作 使用双栈来实现队列,我们就可以让一个栈储存具体元素,另一个栈做辅助  上图可以看到,新元素进栈时,要确保该栈为空.进入栈的元素按顺序存到辅助栈中,等新元素进入栈之后,再将辅助栈中的元素按顺序出到该栈中.

  • 带你了解Java数据结构和算法之栈

    带你了解Java数据结构和算法之栈

    目录 1.栈的基本概念 2.Java模拟简单的顺序栈实现 3.增强功能版栈 4.利用栈实现字符串逆序 5.利用栈判断分隔符是否匹配 6.总结 1.栈的基本概念 栈(英语:stack)又称为堆栈或堆叠,栈作为一种数据结构,是一种只能在一端进行插入和删除操作的特殊线性表.它按照先进后出的原则存储数据,先进入的数据被压入栈底,最后的数据在栈顶,需要读数据的时候从栈顶开始弹出数据(最后一个数据被第一个读出来).栈具有记忆作用,对栈的插入与删除操作中,不需要改变栈底指针. 栈是允许在同一端进行插入和删除操

  • 一起来学习Java的栈和队列

    一起来学习Java的栈和队列

    目录 栈 队列 阻塞队列 双端队列 总结 栈 package com.yuzhenc.collection; import java.util.Stack; /** * @author: yuzhenc * @date: 2022-03-20 15:41:36 * @desc: com.yuzhenc.collection * @version: 1.0 */ public class Test26 { public static void main(String[] args) { Stack

  • Java算法真题详解运用单调栈

    Java算法真题详解运用单调栈

    目录 1.下一个更大元素 题目描述 思路详解 代码与结果 2.每日温度 题目描述 思路详解 代码与结果 3.下一个更大元素II 题目描述 思路详解 代码与结果 1.下一个更大元素 题目描述 思路详解 这一题就选取比较暴力 的解法了. 我们先初始化一个与nums等长度的res数组用来存储结果,我们遍历取出nums中的值,到nums2中寻找,直到找到nums2[j] == nums[i] ,我们再从 nums2的 j 之后遍历找到比nums[i]大的数组返回,找不到就返回-1. 代码与结果 clas

  • Java 回调callback举例详解

    Java 回调callback举例详解

    目录 前言 1.什么是回调 2.例子 第一章.故事的缘起 第二章.幼师的找茬 第三章.幼师回来了 第四章.门口的婆婆 前言 回调的核心就是回调方将本身即this传递给调用方,这样调用方就可以在调用完毕之后告诉回调方它想要知道的信息. 1.什么是回调 软件模块之间总是存在一定的接口,从调用方式上,可以把他们分为三类:同步调用.回调和异步调用. (1)同步调用: 同步调用是最基本并且最简单的一种调用方式,类A的方法a()调用类B的方法b(),一直等待b()方法执行完毕,a()方法再继续往下走.这种调

  • java 归并排序的实例详解

    java 归并排序的实例详解 归并排序 归并排序,指的是将两个已经排序的序列合并成一个序列的操作. 归并操作的过程如下: 申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列 设定两个指针,最初位置分别为两个已经排序序列的起始位置 比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置 重复步骤3直到某一指针到达序列尾 将另一序列剩下的所有元素直接复制到合并序列尾 Java代码 /** * 归并排序 * * @param ts */ @SuppressWa

  • Java ConcurrentHashMap用法案例详解

    一.概念 哈希算法(hash algorithm):是一种将任意内容的输入转换成相同长度输出的加密方式,其输出被称为哈希值. 哈希表(hash table):根据设定的哈希函数H(key)和处理冲突方法将一组关键字映象到一个有限的地址区间上,并以关键字在地址区间中的象作为记录在表中的存储位置,这种表称为哈希表或散列,所得存储位置称为哈希地址或散列地址. 二.HashMap与HashTable 1,线程不安全的HashMap 因为多线程环境下,使用HashMap进行put操作会引起死循环,导致CP

  • Java Collection集合用法详解

    Java Collection集合用法详解

    目录 1.集合的主要体系及分支 1.1Collection集合及实现类 2.List集合(List是带有索引的,所以多注意索引越界等问题) 2.1 List的实现类 3.Set集合 3.1HashSet(Set的实现类) 3.2TreeSet集合(Set的实现类) 4.集合的高频面试题 4.1Arraylist 与 LinkedList 异同 4.2ArrayList 与 Vector 区别 集合框架底层数据结构总结 1.Collection 1.集合的主要体系及分支 1.1Collection

  • Java实现学生管理系统详解流程

    Java实现学生管理系统详解流程

    目录 学生管理系统 项目介绍 JavaSwing 功能展示 使用说明 遇到的问题 JavaWeb 功能展示 使用说明 遇到的问题 最后 学生管理系统 前言:这个是大二做的课设(还是学生管理系统…),理论上虽然是4个人一组一起做的,但是,注意这个“但是”,还是我一个人承担了所有…代码和文档基本都是我一个人写的,当初直接肝得吐血,这也是为啥后面的 Web 版部分功能没有完成的原因. 项目介绍 项目分为一个JavaSwing写的GUI桌面应用和一个半成品的Web应用,下图是项目的整体功能结构展示 Ja

  • Java中的静态内部类详解及代码示例

    1. 什么是静态内部类 在Java中有静态代码块.静态变量.静态方法,当然也有静态类,但Java中的静态类只能是Java的内部类,也称为静态嵌套类.静态内部类的定义如下: public class OuterClass { static class StaticInnerClass { ... } } 在介绍静态内部类之前,首先要弄清楚静态内部类与Java其它内部类的区别. 2. 内部类 什么是内部类?将一个类的定义放在另一个类的内部,就是内部类.Java的内部类主要分为成员内部类.局部内部类.

  • Java多线程ForkJoinPool实例详解

    引言 java 7提供了另外一个很有用的线程池框架,Fork/Join框架 理论 Fork/Join框架主要有以下两个类组成. * ForkJoinPool 这个类实现了ExecutorService接口和工作窃取算法(Work-Stealing Algorithm).它管理工作者线程,并提供任务的状态信息,以及任务的执行信息 * ForkJoinTask 这个类是一个将在ForkJoinPool执行的任务的基类. Fork/Join框架提供了在一个任务里执行fork()和join()操作的机制

  • java HttpServletRequest和HttpServletResponse详解

    java  HttpServletRequest和HttpServletResponse详解 最近由于CAS相关的JAR包的重新封装,所以想尽量做到0配置,而这个过程中大量使 用HttpServletRequest,现在整理如下,以便以后查阅.(表格为从别的地方复制的,排版渣了点,酬和看吧.) 请求与响应相关的类和接口非常多,下表是主要的与请求和接口相关的类以及接口. 主要的与请求和接口相关的类及接口 方    法 说    明 ServletInputStream Servlet的输入流 Se

  • java 抽象类的实例详解

    java 抽象类的实例详解 前言: 什么是抽象类?这名字听着就挺抽象的,第一次听到这个名字还真有可能被唬住.但是,就像老人家所说的,一切反动派都是纸老虎,一切有着装x名字的概念也是纸老虎.好吧,我们已经从战略上做到了藐视它,现在就要战术上重视它,如同要解决纸老虎,就要一个牙齿一个牙齿地敲,一个爪子一个爪子地拔:解决这种抽象概念也一样,先要把它具体化,细分化,然后一个一个地来. 我一般遇到新的概念都会问三个问题: 1.这个东西有什么用?用来干什么的?它的意义在哪里?(显然,如果是没用的东西,就没必

随机推荐