type
status
date
slug
summary
tags
category
icon
password
今日学习清单：
  • 链表与邻接表
  • 栈与队列
  • Kmp
 

1、链表与邻接表：

1、用数组模拟单链表

模板：

测试数据：
  • 详细题目见ACWing的单链表模板题
 

2、用数组模拟双链表

 

2、单调栈：

简要介绍：
单调栈是建立在栈这个数据结构上的一个数据结构，他在一些问题上有着独特的作用，先来介绍一下这个栈
单调栈适用情况：
  • 求解某个元素左边或者右边第一个比它大的元素的下标或者值
 

栈：

一种数据结构，特点是先进后出， 可以想象为是一个有底的罐子，先进去的只能最后出来
栈顶
ㅤ
ㅤ
ㅤ
栈底

单调栈：

单调栈看名字就知道了，是在栈基础上增加了单调性的特点，具体而言是从栈顶到栈底，逐渐增加的叫做单调递增栈，反之叫做单调递减栈
栈顶
0
2
4
6
9
栈底
就类似上面这种，是我们大体的结构，下面是模板

单调递增栈模板

单调递减栈模板：

 
来补充一点内容，在做下面题目的时候，找到一个博客，发现讲得真好，记录一下：

单调栈适用场景：

  • 寻找左侧第一个比当前元素大的元素。
  • 寻找左侧第一个比当前元素小的元素。
  • 寻找右侧第一个比当前元素大的元素。
  • 寻找右侧第一个比当前元素小的元素。
      • 下面具体分析一下：
      1、寻找左侧第一个比当前元素大的元素
      2、寻找左侧第一个比当前元素小的元素
      3、 寻找右侧第一个比当前元素大的元素
      4、 寻找右侧第一个比当前元素小的元素
      上边的分类解法有点绕口，可以简单记为以下条规则：
      他的总结我觉得很好，非常精辟
      原文的链接，写的很好，建议去看看
    • https://blog.csdn.net/zy_dreamer/article/details/131036101

下面直接用具体例子来使用一下： 例题一：

下一个更大元素 I

题目描述：

nums1 中数字 x 的 下一个更大元素 是指 x 在 nums2 中对应位置 右侧 的 第一个 比 x 大的元素。
给你两个 没有重复元素 的数组 nums1 和 nums2 ，下标从 0 开始计数，其中nums1 是 nums2 的子集。
对于每个 0 <= i < nums1.length ，找出满足 nums1[i] == nums2[j] 的下标 j ，并且在 nums2 确定 nums2[j] 的 下一个更大元素 。如果不存在下一个更大元素，那么本次查询的答案是 -1 。
返回一个长度为 nums1.length 的数组 ans 作为答案，满足 ans[i] 是如上所述的 下一个更大元素 。
示例 1：
示例 2：

题解：

正好符合我们上面说的哪个弹出栈的时候是我们需要的
 

例题二：

题目描述：

给定一个循环数组 nums （ nums[nums.length - 1] 的下一个元素是 nums[0] ），返回 nums 中每个元素的 下一个更大元素 。
数字 x 的 下一个更大的元素 是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1 。
示例 1:
示例 2:

题解：

此题关键在于对于循环搜索可以考虑一下循环两次来计算
 

3、单调队列：

单调队列适用的题目是滑动窗口类题目
 

模板书写流程：

1、如果窗口的队列的长度大于k，弹出第一个直接pop(0)
2、while循环，如果不为空并且序列最后面的值大于下一个值就弹出最后一个值
3、存储当前的i，这个是每一步都要进行地操作
4、如果i大于k地时候纪要开始记录了，res地值

单调序列求最大值模板：

 

单调队列求最小值模板

 
相关例题：

例题一：

滑动窗口最大值
  • ‣
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。
示例 1：
示例 2：
 
题解：
 

例题二：

子矩阵
给定一个 n×mn×m （nn 行 mm 列）的矩阵。
设一个矩阵的价值为其所有数中的最大值和最小值的乘积。
求给定矩阵的所有大小为 a×ba×b （aa 行 bb 列）的子矩阵的价值的和。
答案可能很大，你只需要输出答案对 998244353998244353 取模后的结果。
输入格式
输入的第一行包含四个整数分别表示 n,m,a,bn,m,a,b，相邻整数之间使用一个空格分隔。
接下来 nn 行每行包含 mm 个整数，相邻整数之间使用一个空格分隔，表示矩阵中的每个数 Ai,jAi,j。
输出格式
输出一行包含一个整数表示答案。
数据范围
对于 40%40% 的评测用例，1≤n,m≤1001≤n,m≤100；
对于 70%70% 的评测用例，1≤n,m≤5001≤n,m≤500；
对于所有评测用例，1≤a≤n≤10001≤a≤n≤1000，1≤b≤m≤10001≤b≤m≤1000，1≤Ai,j≤1091≤Ai,j≤109。
输入样例：
输出样例：
样例解释
1×2+2×3+4×5+5×6=58 1×2+2×3+4×5+5×6=58。
 
 
 
 

4、KMP

 
 
 
 
 
10.18二分法专项10.12算法学习模板之前缀和
Loading...