一、算法描述 本篇文章讲述的数据结构是单调栈，是一种和单调队列类似的数据结构（下一篇文章会讲到）。 单调队列主要用于\(O(n)\)解决滑动窗口问题，单调栈主要用于\(O(n)\)解决NGE问题(NextGreaterElement)，也就是对序列中的每个元素，找到上（下）一个比它大（小）的元素，原理相同。 以下面的题目为例，找到左边第一个比它小的元素： 我们可以发现，如果当前元素比左边的数小，那么那些左边的数就不会作为答案输出。 所以我们可以维护一个栈，当遇到新元素时，只要栈不为空且当前元素≤栈顶元素，就一直弹出栈顶元素，最后将当前元素入栈。这样形成的一个栈就是单调递增的，答案也就是当前栈顶...

一、算法描述 本篇文章讲述的数据结构是单调队列，主要用于解决滑动窗口类问题的数据结构，即，在长度为\(n\)的序列中，求每个长度为\(m\)的区间的区间最值，时间复杂度\(O(n)\)。 思路如下： 用一个队列\(q[N]\)来存储可能是答案的下标。 先判断是否滑出了窗口，如果滑出了则删除队头元素\(q[hh]\)。 \(q[hh]\)相比于队列中其他元素是最早进来的，所以判断是否在滑动窗口内用\(q[hh]\)来判断 如果队列中没有元素，\(i\)刚好成为\(q[hh]\) 如果队列中已经存储了元素，\(q[hh]\)比\(i\)早进入队列 所以\(q[hh]\)是最早进入队列的 ...

一、算法描述 本篇文章水平不够，讲不清楚KMP到底是怎么回事，以后再更新一下。 本篇文章讲述的是KMP算法，一个著名的字符串匹配算法，效率很高，\(O(n)\)的时间复杂度。 难点在于：如何理解\(next[i]\)★★★ \(ne[i]=j\)表示，\(p[1j]=p[ij+1,i]\)，从\(1\)到\(j\)的前缀串，完全等于，从\(ij+1\)到\(i\)的后缀串。 当匹配道某一位置时，下一个位置不匹配，此时为了节约时间，我们要找到一个位置，使得，匹配不成功的点能够继续匹配 暴力做法是往后移动一位，而KMP是直接滑到能够滑到的最远的位置，或者说最少回退多少能够继续匹配。 二、题目描述 ...

一、题目来源 AcWing算法基础课-3302.表达式求值 二、题目描述 给定一个表达式，其中运算符仅包含+,-,,/（加减乘整除），可能包含括号，请你求出表达式的最终值。 注意： 数据保证给定的表达式合法。 题目保证符号只作为减号出现，不会作为负号出现，例如，-1+2,(2+2)(-(1+1)+2)之类表达式均不会出现。 题目保证表达式中所有数字均为正整数。 题目保证表达式在中间计算过程以及结果中，均不超过\(2^{31}1\)。 题目中的整除是指向\(0\)取整，也就是说对于大于\(0\)的结果向下取整，例如\(5/3=1\)，对于小于\(0\)的结果向上取整，例如\(5/(1−4)...

一、算法描述 本篇文章讲述的数据结构是，队列，数组模拟队列，也不是循环队列。 队列的结构，完全就是学校食堂排队打饭的那个队列。一个队头，一个队尾，从队头出，从队尾进，排队打饭也是这样hhh。 //用数组模拟的队列定义如下： inthh,tt; intq[N]; / hh表示队头，tt表示队尾（我习惯于表示队尾的下一个位置，可以根据个人习惯来修改） q[N]表示队列 / 队列和栈一样，也不是很难理解的数据结构，重点还是要熟悉应用。 接下来介绍队列的各种操作： 初始化操作： voidinit() { hh=tt=0; } 看个人习惯，我习惯于\(tt\)表示队尾的下一个位置，如果表示...

一、算法描述 本篇文章讲述的数据结构是双链表，与上一篇文章一样是算法竞赛中常用的用数组模拟的双链表。 //用数组模拟的双链表定义如下： inte[N],l[N],r[N],idx; / e[i]表示节点i的值 l[i]表示节点i的左边一个节点 r[i]表示节点i的右边一个节点 idx表示当前用到了哪个节点 / 跟单链表差不多。 多画图，多思考。 接下来介绍双链表的各种操作： 初始化操作： voidinit() { r[0]=1,l[1]=0,idx=2; } 以\(0\)和\(1\)为两个界限，初始状态就是\(0\)的右边是\(1\)，\(1\)的左边是\(0\)。 要注意...

一、算法描述 本篇文章讲述的数据结构是，栈，数组模拟栈。 栈的结构相信大家应该很清楚了，特点就是先进后出，只能在栈顶操作，栈底不能操作。 //用数组模拟的栈定义如下： inttt; intst[N]; / tt表示栈顶（我习惯于表示栈顶的下一个位置，可以根据个人习惯来修改） st[N]表示栈 / 栈不是很难理解，相比于链表要简单很多，后面的队列和栈一样不是很难理解。 接下来介绍栈的各种操作： 初始化操作： voidinit() { tt=0; } 看个人习惯，我习惯于表示栈顶元素的下一个位置，如果是表示栈顶初始化应修改为\(tt=-1\); 向栈中压入元素： voidpush...

一、算法描述 含义 双指针，指的是在遍历对象的过程中，不是普通的使用单个指针进行访问，而是使用两个相同方向（快慢指针）或者相反方向（对撞指针）的指针进行扫描，从而达到相应的目的。 另外还可以根据序列进行区分，例如在快排中，双指针指向的是同一个序列，而归并排序中两个指针指向的是两个不同的序列。 怎么用 没有必要对概念区分的很清楚，只需要知道怎么使用即可。 首先想暴力解法，然后在暴力解法的基础之上，发现性质，进行优化。 通过题目来理解什么是双指针吧。 二、题目描述 给定一个长度为\(n\)的整数序列，请找出最长的不包含重复的数的连续区间，输出它的长度。 输入格式 第一行包含整数\(n\)。...

一、题目来源 AcWing算法基础课-800.数组元素的目标和 二、题目描述 给定两个升序排序的有序数组\(A\)和\(B\)，以及一个目标值\(x\)。 数组下标从\(0\)开始。 请你求出满足\(A[i]+B[j]=x\)的数对\((i,j)\)。 数据保证有唯一解。 输入格式 第一行包含三个整数\(n,m,x\)分别表示\(A\)的长度，\(B\)的长度以及目标值\(x\)。 第二行包含\(n\)个整数，表示数组\(A\)。 第三行包含\(m\)个整数，表示数组\(B\)。 输出格式 共一行，包含两个整数\(i\)和\(j\)。 数据范围 数组长度不超过\(10^5\)。同一数组内元...