浅谈单调队列、单调栈

初谈这个话题，相信许多人会有一种似有所悟，但又不敢确定的感觉。没错，这正是因为其中“单调”一词的存在，所谓单调是什么，学过函数的people都知道单调函数或者函数的单调性，直白一点说单调就是一直增或一直减。例如：1，3，5，9就是一个单调增数列，数列中不存在后一个数比前一个数小的现象。那么同样，在这里谈到的话题也有类似特点。

先说一下单调队列吧!      单调队列，就是一个符合单调性质的队列，它同时具有单调的性质以及队列的性质。他在编程中使用频率不高，但却占有至关重要的地位。它的作用很简单，就是为了维护一组单调数据，让我们在运行的过程中能够快速寻求前k个或后k个中最大或最小的值。    至于单调栈，相信看完上面的叙述后，都会有一个大概的理解，单调栈就是一个符合单调性质的栈它同时具有单调的性质以及栈的性质。在作用方面两者是相同的，差别仅是在编程过程中所维护的数组的方式不同。

下面我会举个简单的列子来解释单调队列及单调栈。

例题：有一组数据1，5，9，4，7，8，6，他们会依此输入，同时，在某一时刻会让你求出后n个数中的最大值。

根据题意，我们可以得出这样一个结论，若后一个数大于前一个数，则结果必定不会是前一个数（比如现在输入了1，5，由于1<5，所以无论是后几个数中的最大值均不会为1），因此，我们只需维护一个单调递减的数组便可快速求得所需之。（数组变化如下：输入——1，数组——1；输入——5，由于5>1删去1添入5，数组——5；输入——9，由于9>5删去5添入9，数组——9；输入——4，由于4<9直接添入，数组——9,4；输入——7，由于7>4同时7<9因此删去4添入7，数组——9,7；输入——8，由于8>4同时8<9因此删去7添入8，数组——9,8；输入——6，由于6<8直接添入，数组——9,8,6。）

单调队列及单调栈的基础也就这些，剩下的就只剩下个人理解及练习了。推荐几道题，在大视野上的1012以及1047，其中1012比较裸适合初学者做，1047略有难度推荐做完1012后再做。（在这里给个提示，1047要用到两次单调队列、单调栈，横着一次再用结果竖这一次。）

以上就是本文的全部内容了，希望对你有所帮助。

赞 (0)

相关推荐

  • jsp页面获取服务器时间的简单调用示例

    Calendar c = Calendar.getInstance(); int year = c.get(Calendar.YEAR); int month = c.get(Calendar.MONTH); int day= c.get(Calendar.DAY); 这三行加在<% %>里面 调用时用<%= year %><%= month%><%= day%>

  • 使用PDB简单调试Python程序简明指南

    使用PDB简单调试Python程序简明指南

    在 Python 中也可以像 gcc/gdb 那样调试程序,只要在运行 Python 程序时引入 pdb 模块(假设要调试的程序名为 d.py): 复制代码 代码如下: $ vi d.py #!/usr/bin/python def main():         i, sum = 1, 0         for i in xrange(100):                 sum = sum + i         print sum if __name__ == '__main__'

  • 浅谈Laravel队列实现原理解决问题记录

    问题 公司项目使用Laravel的开发的两个项目在同一个测试服务器部署,公用同一个redis.在使用laravel中的队列时,产生冲突干扰. 查找问题原因 在laravel 队列的操作类Illuminate\Queue\RedisQueue.php中可以看到pushRaw()方法: // 将一任务推入队列中 public function pushRaw($payload, $queue = null, array $options = []) { $this->getConnection()-

  • 浅谈单调队列、单调栈

    初谈这个话题,相信许多人会有一种似有所悟,但又不敢确定的感觉.没错,这正是因为其中"单调"一词的存在,所谓单调是什么,学过函数的people都知道单调函数或者函数的单调性,直白一点说单调就是一直增或一直减.例如:1,3,5,9就是一个单调增数列,数列中不存在后一个数比前一个数小的现象.那么同样,在这里谈到的话题也有类似特点. 先说一下单调队列吧!      单调队列,就是一个符合单调性质的队列,它同时具有单调的性质以及队列的性质.他在编程中使用频率不高,但却占有至关重要的地位.它的作用

  • C语言 浅谈栈与队列的定义与操作

    C语言 浅谈栈与队列的定义与操作

    目录 栈的定义 栈的实现 前置 初始化栈 栈的销毁 栈的插入 出栈的操作 取栈顶元素 栈的大小 队列的定义 队列的基本操作 队列的初始化 队列的销毁 队列的插入 队列的删除 队列的判空 取出队头元素 取出队尾元素 队列的大小 栈的定义 栈同样是一种线性表,它的特性是插入元素必须从后面插入,删除元素也是从后面删除,进行数据删除和插入的一端称为栈顶,另一端是栈底. 压栈-就是插入元素 出栈-就是删除元素 它可以用数组实现也可以用链表实现 但是用数组实现更好,因为链表的插入和删除要进行遍历,而数组可以

  • 浅谈C语言函数调用参数压栈的相关问题

    参数入栈的顺序 以前在面试中被人问到这样的问题,函数调用的时候,参数入栈的顺序是从左向右,还是从右向左.参数的入栈顺序主要看调用方式,一般来说,__cdecl 和__stdcall 都是参数从右到左入栈. 看下面的代码: #include <stdio.h> int test(int a, int b) { printf("address of a %x.\n", &a); printf("address of b %x.\n", &b)

  • 浅谈从Java中的栈和堆,进而衍生到值传递

    简述Java中的栈和堆,变量和对象的地址存放和绑定机制 初学java的小白,很多人都搞不清楚java中堆和栈的概念,我们都知道计算机只能识别二进制字节码文件,如果分不清楚对象和变量在内存的地址分配,也就是堆和栈的问题,很多问题比如绑定机制.静态方法.实例方法.局部变量的作用域就会搞不清楚. 首先记住结论: 基本数据类型.局部变量.String类型的直接赋值都是存放在栈内存中的,用完就消失. new创建的实例化对象.String类型的构造方法new出来的对象及数组,是存放在堆内存中的,用完之后靠垃

  • 浅谈鸿蒙 JavaScript GUI 技术栈

    作者:doodlewind 链接:https://juejin.im/post/6872154561574862855 众所周知,刚刚开源的「鸿蒙 2.0」以 JavaScript 作为 IoT 应用开发的框架语言.这标志着继 SpaceX 上天之后,JavaScript 再一次蹭到了新闻联播级的热点.这么好的机会,只拿来阴阳怪气实在太可惜了.作为科普,这篇文章不会拿着放大镜找出代码中的槽点来吹毛求疵,而是希望通俗地讲清楚它所支持的 GUI 到底是怎么一回事.只要对计算机基础有个大概的了解,应该

  • 浅谈C++STL之双端队列容器

    浅谈C++STL之双端队列容器

    概述 deque块在头部和尾部都可以插入和删除.而不需要移动任何元素,而不需要移动其他元素(使用push_back()方法在尾部插入元素,会扩张队列,而使用push_front()方法在首部插入元素和使用insert()方法在中间插入元素,只是将原位置上的元素进行覆盖,不会增加新元素)一般来说,当考虑到容器元素的内存分配策略和操作的性能时deque相当于vector更有优势. 创建deque对象与vector类似 插入元素 使用push_back()方法从尾部插入元素,会不断扩张队列. #inc

  • 浅谈多线程_让程序更高效的运行

    浅谈多线程_让程序更高效的运行

    Java Thread 的一些认识: Java是抢占式线程,一个线程就是进程中单一的顺序控制流,单个进程可以拥有多个并发任务,其底层是切分CPU时间,多线程和多任务往往是使用多处理器系统的最合理方式 进程可以看作一个程序或者一个应用:线程是进程中执行的一个任务,多个线程可以共享资源 一个Java 应用从main 方法开始运行,main 运行在一个线程内,也被称为 "主线程",Runnable也可以理解为Task (任务) JVM启动后,会创建一些守护线程来进行自身的常规管理(垃圾回收,

  • 浅谈MySQL和Lucene索引的对比分析

    浅谈MySQL和Lucene索引的对比分析

    MySQL和Lucene都可以对数据构建索引并通过索引查询数据,一个是关系型数据库,一个是构建搜索引擎(Solr.ElasticSearch)的核心类库.两者的索引(index)有什么区别呢?以前写过一篇<Solr与MySQL查询性能对比>,只是简单的对比了下查询性能,对于内部原理却没有解释,本文简单分析下两者的索引区别. MySQL索引实现 在MySQL中,索引属于存储引擎级别的概念,不同存储引擎对索引的实现方式是不同的,本文主要讨论MyISAM和InnoDB两个存储引擎的索引实现方式. M

  • 浅谈Java中常用数据结构的实现类 Collection和Map

    线性表,链表,哈希表是常用的数据结构,在进行Java开发时,JDK已经为我们提供了一系列相应的类来实现基本的数据结构.这些类均在java.util包中.本文试图通过简单的描述,向读者阐述各个类的作用以及如何正确使用这些类. Collection ├List │├LinkedList │├ArrayList │└Vector │ └Stack └Set Map ├Hashtable ├HashMap └WeakHashMap Collection接口 Collection是最基本的集合接口,一个C

随机推荐