0%

优先队列(堆)

优先队列也就是堆

什么是堆呢?

堆是一颗完全二叉树,树中每个结点的值都不小于(或不大于)其左右孩子的值。 如果父亲结点是大于等于左右孩子就是大顶堆,小于等于左右孩子就是小顶堆。

priority_queue<int , vector<int>,greater<int>> heap;//创建小根堆
1
2
3
4
5
6
7
8
9
10
11

引用头文件 #include<queue>
top 访问队头元素
empty 队列是否为空
size 返回队列内元素个数
push 插入元素到队尾 (并排序)
emplace 原地构造一个元素并插入队列
pop 弹出队头元素
swap 交换内容


1
2
3
4
5
6
7
8
9
10
11
12
13
14
std::priority_queue<T> pq;
std::priority_queue<T, std::vector<T>, cmp> pq;

//自定义比较类型
//左大于右就会建立小顶堆,反而建立大顶堆

// 小顶堆--pair类型的比较
class mycomparison {
public:
bool operator()(const pair<int, int>& lhs, const pair<int, int>& rhs) {
return lhs.second > rhs.second;
}
};

练习题目

Leetcode-前K个高频元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public:
// 小顶堆
class mycmp{
public:
bool operator() (const pair<int,int> &l,const pair<int,int> &r)
{
return l.second>r.second;
}
};
vector<int> topKFrequent(vector<int>& nums, int k) {
unordered_map<int,int> map;
priority_queue<pair<int,int>,vector<pair<int,int>>,mycmp> heap;
for(int i=0;i<nums.size();++i)
{
++map[nums[i]];
}
for(auto i : map){
heap.push(i);
if(heap.size()>k)
{
heap.pop();
}
}
vector<int> ans;

while(!heap.empty())
{
ans.push_back(heap.top().first);
heap.pop();
}
return ans;
}
};

位运算

乘以2的m次方

1
x << m

除以2的m次方

1
x >> m

判断一个数的奇偶性

1
(n & 1) == 1//true为奇数,false为偶数

不用临时变量交换两个数

1
2
3
4
5
a ^= b ^= a ^= b;     
//或者,一样
a ^= b;
b ^= a;
a ^= b;

取绝对值

1
(n ^ (n >> 31)) - (n >> 31)

从低位到高位,取n的第m位

1
(n >> (m-1)) & 1;  

消去x最后一个的1

1
x&(x-1)

十进制数10的二进制为1010,9的二进制数为1001,那么(1010)&(1001)=1000,现在10的二进制中最后一位的1已经被消去

可以计算一个数的二进制中1的个数

1
2
3
4
5
6
7
8
9
10
int bitcount (unsigned int n)
{
int count=0 ;
while (n) {
count++ ;
n &= (n - 1) ;
}
return count ;
}

前缀和

前缀和的思路是这样的,对于一个给定的数组 nums,我们额外开辟一个前缀和数组进行预处理:

1
2
3
4
5
6
int n = nums.length;
// 前缀和数组
int[] preSum = new int[n + 1];
preSum[0] = 0;
for (int i = 0; i < n; i++)
preSum[i + 1] = preSum[i] + nums[i];

20210811132123

这个前缀和数组 preSum 的含义也很好理解,preSum[i] 就是 nums[0..i-1] 的和。那么如果我们想求 nums[i..j] 的和,只需要一步操作 preSum[j+1]-preSum[i] 即可,而不需要重新去遍历数组了。

回到这个子数组问题,我们想求有多少个子数组的和为 k,借助前缀和技巧很容易写出一个解法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int subarraySum(int[] nums, int k) {
int n = nums.length;
// 构造前缀和
int[] sum = new int[n + 1];
sum[0] = 0;
for (int i = 0; i < n; i++)
sum[i + 1] = sum[i] + nums[i];
int ans = 0;
// 穷举所有子数组
for (int i = 1; i <= n; i++)
for (int j = 0; j < i; j++)
// sum of nums[j..i-1]
if (sum[i] - sum[j] == k)
ans++;
return ans;
}

这个解法的时间复杂度 $O(N^2)$ 空间复杂度 $O(N)$ ,并不是最优的解法。不过通过这个解法理解了前缀和数组的工作原理之后,可以使用一些巧妙的办法把时间复杂度进一步降低。

优化

前面的解法有嵌套的 for 循环:

1
2
3
4
5
for (int i = 1; i <= n; i++)
for (int j = 0; j < i; j++)
if (sum[i] - sum[j] == k)
ans++;

第二层 for 循环在干嘛呢?翻译一下就是,在计算,有几个 j 能够使得 sum[i] 和 sum[j] 的差为 k。毎找到一个这样的 j,就把结果加一。

我们可以把 if 语句里的条件判断移项,这样写:

1
2
if (sum[j] == sum[i] - k)
ans++;

优化的思路是:我直接记录下有几个 sum[j]sum[i] - k 相等,直接更新结果,就避免了内层的 for 循环。我们可以用哈希表,在记录前缀和的同时记录该前缀和出现的次数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int subarraySum(int[] nums, int k) {
int n = nums.length;
// map:前缀和 -> 该前缀和出现的次数
HashMap<Integer, Integer>
preSum = new HashMap<>();
// base case
preSum.put(0, 1);
int ans = 0, sum0_i = 0;
for (int i = 0; i < n; i++) {
sum0_i += nums[i];
// 这是我们想找的前缀和 nums[0..j]
int sum0_j = sum0_i - k;
// 如果前面有这个前缀和,则直接更新答案
if (preSum.containsKey(sum0_j))
ans += preSum.get(sum0_j);
// 把前缀和 nums[0..i] 加入并记录出现次数
preSum.put(sum0_i,
preSum.getOrDefault(sum0_i, 0) + 1);
}
return ans;
}

比如说下面这个情况,需要前缀和 8 就能找到和为 k 的子数组了,之前的暴力解法需要遍历数组去数有几个 8,而优化解法借助哈希表可以直接得知有几个前缀和为 8。

20210811134248

这样,就把时间复杂度降到了 $O(N)$,是最优解法了。

总结

前缀和不难,却很有用,主要用于处理数组区间的问题。

比如说,让你统计班上同学考试成绩在不同分数段的百分比,也可以利用前缀和技巧:

1
2
3
4
5
6
7
8
9
int[] scores; // 存储着所有同学的分数
// 试卷满分 150 分
int[] count = new int[150 + 1]
// 记录每个分数有几个同学
for (int score : scores)
count[score]++
// 构造前缀和
for (int i = 1; i < count.length; i++)
count[i] = count[i] + count[i-1];

这样,给你任何一个分数段,你都能通过前缀和相减快速计算出这个分数段的人数,百分比也就很容易计算了。

但是,稍微复杂一些的算法问题,不止考察简单的前缀和技巧。比如本文探讨的这道题目,就需要借助前缀和的思路做进一步的优化,借助哈希表去除不必要的嵌套循环。可见对题目的理解和细节的分析能力对于算法的优化是至关重要的。

二维前缀和

二维前缀和就是求一个矩阵的和

但是怎么来求呢?

20210811143617

就如图中

知道了两个点的位置和他们的二维前缀和,

图中红色是左上角的那个点的二维前缀和,

红色+黄色部分是右下角的那个点的二维前缀和,

是不是可以用这个来求出他们之间的矩阵的和呢?

也就是这一部分:

20210811143707

图中黑色的部分就是我们要求的那个矩阵和

看到这里yy一下

是不是可以通过某些奇怪的方法求出黑色部分是多少?

20210811143730

D点表示的二维前缀和值是红色部分+两个黄色部分+黑色部分

A点表示的是红色部分

B点表示的是上面的黄色部分+红色部分

C点表示的是下面的黄色部分+红色部分

这样是不是发现有什么神奇的东西快要出现了

这里面只有D的前缀和里面包括黑色部分

只要减去D里面的哪两个黄色部分和红色部分是不是就剩下了我们要求的黑色部分了?

那怎么减去呢?

可以这样:

D - B - C + A

这就是二维前缀和最重要的部分了

化成二维数组的形式就是这样的

$f[i][j]−f[i−1][j]−f[i][j−1]+f[i−1][j−1]$

二维前缀和怎么求

这个可以类比上面求矩阵的思想

只是这个矩阵的右下角是(i,j),左上角也是(i,j)

就是一个11的矩阵

所以也是很好求的

但是上面是已知D,A,B,C求黑色部分

这里你只知道A,B,C和黑色部分

因为是一个11的矩阵吗

所以黑色部分就只有一个元素也就是(i,j)坐标上的那个元素值

所以就可以个加法变减法,减法变加法一个性质的

通过A,B,C和黑色部分来求出D

所以D就可以等于B+C-D+黑色部分:

上面的黄色部分+红色部分+下面的黄色部分+红色部分-红色部分+黑色部分
=上面的黄色部分+红色部分+下面的黄色部分+黑色部分

刚好等于D

方程式为

$f[i][j]=f[i−1][j]+f[i][j−1]−f[i−1][j−1]+a[i][j]$

模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include<iostream>
#include<cstdio>
#define int long long
using namespace std;
const int Max = 1003;
int a[Max][Max];
int f[Max][Max];
signed main()
{
freopen("acioi.in","r",stdin);
int n,m,c;
cin >> n >> m >> c;
for(register int i = 1;i <= n;++ i)
for(register int j = 1;j <= m;++ j)
cin >> a[i][j],f[i][j] = f[i - 1][j] + f[i][j - 1] - f[i - 1][j - 1] + a[i][j];
int k;
cin >> k;
for(register int i = 1;i <= k;++ i)
{
int x1,x2,y1,y2;//x1,y1是左上角的坐标,另一对是右下角的坐标
cin >> x1 >> y1 >> x2 >> y2;
cout << f[x2][y2] - f[x1 - 1][y2] - f[x2][y1 - 1] + f[x1 - 1][y1 - 1];
}
cout << M << endl;
return 0;
}

差分

差分可以简单的看成序列中每个元素与其前一个元素的差。

原数组 进行差分,得到差分数组 ,差分数组求前缀和,又得到原数组

差分数组改变–再求前缀和,得到改变后的数组

1
2
5,6, 4,8, 7, 6,9
5 1 -2 4 -1 -1 3

一维差分

让一个序列中某个区间内的所有值均加上或减去一个常数。

假如在 3~8 的区间上加上 5,那我们在差分数组中的 3 位置上加上一个 5 ,再在8+1的位置上减一个5

1
2
3
4
5
//区间[l,r]中的所有值都加上常数c
b[l] += c;
b[r+1] -= c;

//每次求前缀和都会有 b[l]+c,得到A[i]只需要加上1个C

二维差分

20210811145147

根据二维前缀和表示的是左上角矩形的和,由于差分只涉及前面相邻的数(由一维可以推出),并且由前面范围的数相加得到这个位置的数。那么类比二维前缀和和一维差分,可以简单推测出二维差分的公式

$p[i][j]=a[i][j]-a[i-1][j]-a[i][j-1]+a[i-1][j-1]$

如何从差分矩阵得到原/改变矩阵呢?可以参考下面公式(二维前缀和)

$f[i][j]=f[i−1][j]+f[i][j−1]−f[i−1][j−1]+p[i][j]$

即可以得到改变后的矩阵

比如,我们有一个矩阵 a,如下所示:

1
2
3
1 2 4 3
5 1 2 4
6 3 5 9

那么对应的二维差分矩阵 p 如下:

1
2
3
1  1  2 -1
4 -5 -1 3
1 1 1 2

应用

如果我们要在左上角是 (x1,y1),右下角是 (x2,y2) 的矩形区间每个值都 +a,如下图所示

20210811150918

在我们要的区间开始位置(x1,y1)处 +c,根据前缀和的性质,那么它影响的就是整个黄色部分,多影响了两个蓝色部分,所以在两个蓝色部分 -c 消除 +c 的影响,而两个蓝色部分重叠的绿色部分多了个 -c 的影响,所以绿色部分 +c 消除影响。所以对应的计算方法如下:

1
2
3
4
diff[x1][y1] += c;
diff[x1][y2+1] -=c;
diff[x2+1][y1] -=c;
diff[x2+1][y2+1] += c;

最后在求前缀和 回去就行

双指针

我把双指针技巧再分为两类,一类是「快慢指针」,一类是「左右指针」。前者解决主要解决链表中的问题,比如典型的判定链表中是否包含环;后者主要解决数组(或者字符串)中的问题,比如二分查找。

快慢指针

快慢指针一般都初始化指向链表的头结点 head,前进时快指针 fast 在前,慢指针 slow 在后,巧妙解决一些链表中的问题。

判定链表中是否含有环

单链表的特点是每个节点只知道下一个节点,所以一个指针的话无法判断链表中是否含有环的。

如果链表中不含环,那么这个指针最终会遇到空指针 null 表示链表到头了,这还好说,可以判断该链表不含环。

1
2
3
4
5
6

boolean hasCycle(ListNode head) {
while (head != null)
head = head.next;
return false;
}

但是如果链表中含有环,那么这个指针就会陷入死循环,因为环形数组中没有 null 指针作为尾部节点。

经典解法就是用两个指针,一个跑得快,一个跑得慢。如果不含有环,跑得快的那个指针最终会遇到 null,说明链表不含环;如果含有环,快指针最终会超慢指针一圈,和慢指针相遇,说明链表含有环。

1
2
3
4
5
6
7
8
9
10
boolean hasCycle(ListNode head) {
ListNode fast, slow;
fast = slow = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
if (fast == slow) return true;
}
return false;
}

已知链表中含有环,返回这个环的起始位置

20210811151709

这个问题一点都不困难,有点类似脑筋急转弯,先直接看代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
ListNode detectCycle(ListNode head) {
ListNode fast, slow;
fast = slow = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
if (fast == slow) break;
}
// 上面的代码类似 hasCycle 函数
slow = head;
while (slow != fast) {
fast = fast.next;
slow = slow.next;
}
return slow;
}

可以看到,当快慢指针相遇时,让其中任一个指针指向头节点,然后让它俩以相同速度前进,再次相遇时所在的节点位置就是环开始的位置。这是为什么呢?

第一次相遇时,假设慢指针 slow 走了 k 步,那么快指针 fast 一定走了 2k 步,也就是说比 slow 多走了 k 步(也就是环的长度)。
20210811151935

设相遇点距环的起点的距离为 m,那么环的起点距头结点 head 的距离为 k - m,也就是说如果从 head 前进 k - m 步就能到达环起点。

巧的是,如果从相遇点继续前进 k - m 步,也恰好到达环起点。

20210811151947

所以,只要我们把快慢指针中的任一个重新指向 head,然后两个指针同速前进,k - m 步后就会相遇,相遇之处就是环的起点了

寻找链表的中点

类似上面的思路,我们还可以让快指针一次前进两步,慢指针一次前进一步,当快指针到达链表尽头时,慢指针就处于链表的中间位置

1
2
3
4
5
6
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
// slow 就在中间位置
return slow;

当链表的长度是奇数时,slow 恰巧停在中点位置;如果长度是偶数,slow 最终的位置是中间偏右:

20210811163211

寻找链表中点的一个重要作用是对链表进行归并排序。

回想数组的归并排序:求中点索引递归地把数组二分,最后合并两个有序数组。对于链表,合并两个有序链表是很简单的,难点就在于二分。

但是现在你学会了找到链表的中点,就能实现链表的二分了。关于归并排序的具体内容本文就不具体展开了。

寻找链表的倒数第 k 个元素

我们的思路还是使用快慢指针,让快指针先走 k 步,然后快慢指针开始同速前进。这样当快指针走到链表末尾 null 时,慢指针所在的位置就是倒数第 k 个链表节点(为了简化,假设 k 不会超过链表长度):

1
2
3
4
5
6
7
8
9
ListNode slow, fast;
slow = fast = head;
while (k-- > 0)
fast = fast.next;
while (fast != null) {
slow = slow.next;
fast = fast.next;
}
return slow;

左右指针的常用算法

左右指针在数组中实际是指两个索引值,一般初始化为 left = 0, right = nums.length - 1 。

二分查找

前文「二分查找」有详细讲解,这里只写最简单的二分算法,旨在突出它的双指针特性:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int binarySearch(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while(left <= right) {
int mid = (right + left) / 2;
if(nums[mid] == target)
return mid;
else if (nums[mid] < target)
left = mid + 1;
else if (nums[mid] > target)
right = mid - 1;
}
return -1;
}

两数之和

20210811170839

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int[] twoSum(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left < right) {
int sum = nums[left] + nums[right];
if (sum == target) {
// 题目要求的索引是从 1 开始的
return new int[]{left + 1, right + 1};
} else if (sum < target) {
left++; // 让 sum 大一点
} else if (sum > target) {
right--; // 让 sum 小一点
}
}
return new int[]{-1, -1};
}

反转数组

1
2
3
4
5
6
7
8
9
10
11
void reverse(int[] nums) {
int left = 0;
int right = nums.length - 1;
while (left < right) {
// swap(nums[left], nums[right])
int temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
left++; right--;
}
}

滑动窗口算法

这也许是双指针技巧的最高境界了,如果掌握了此算法,可以解决一大类子字符串匹配的问题,不过「滑动窗口」稍微比上述的这些算法复杂些。

幸运的是,这类算法是有框架模板的,而且这篇文章就讲解了「滑动窗口」算法模板,帮大家秒杀几道 LeetCode 子串匹配的问题。

单调队列

也许这种数据结构的名字你没听过,其实没啥难的,就是一个「队列」,只是使用了一点巧妙的方法,使得队列中的元素单调递增(或递减)。这个数据结构有什么用?可以解决滑动窗口的一系列问题。

单调队列是一种主要用于解决滑动窗口类问题的数据结构,即,在长度为 n 的序列中,求每个长度为 n 的区间的区间最值

题目

理解

在一堆数字中,已知最值,如果给这堆数添加一个数,那么比较一下就可以很快算出最值;但如果减少一个数,就不一定能很快得到最值了,而要遍历所有数重新找最值。

回到这道题的场景,每个窗口前进的时候,要添加一个数同时减少一个数,所以想在 O(1) 的时间得出新的最值,就需要「单调队列」这种特殊的数据结构来辅助了。

一个普通的队列

1
2
3
4
5
6
7
8
class Queue
{
void push(int n);
// 或 enqueue,在队尾加入元素 n

void pop();
// 或 dequeue,删除队头元素
}

单调队列操作

1
2
3
4
5
6
7
8
9
10
11
class MonotonicQueue
{
// 在队尾添加元素 n
void push(int n);

// 返回当前队列中的最大值
int max();

// 队头元素如果是 n,删除它
void pop(int n);
}

当然,这几个 API 的实现方法肯定跟一般的 Queue 不一样,不过我们暂且不管,而且认为这几个操作的时间复杂度都是 O(1),先把这道「滑动窗口」问题的解答框架搭出来:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
vector<int> maxSlidingWindow(vector<int>& nums,int k)
{
MonotonicQueue window;
vector<int> res;
for(int i =0; i < nums.size(); i++)
{
if(i < k -1)
{//先把窗口的前 k - 1 填满
window.push(nums[i]);
}
else
{// 窗口开始向前滑动
window.push(nums[i]);
res.push_back(window.max());
window.pop(nums[i - k +1]);
// nums[i - k + 1] 就是窗口最后的元素
}
}
return res;
}

20210809212742

实现单调队列

首先我们要认识另一种数据结构:deque,即双端队列。很简单:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class deque {
// 在队头插入元素 n
void push_front(int n);
// 在队尾插入元素 n
void push_back(int n);
// 在队头删除元素
void pop_front();
// 在队尾删除元素
void pop_back();
// 返回队头元素
int front();
// 返回队尾元素
int back();
}

而且,这些操作的复杂度都是 O(1)。这其实不是啥稀奇的数据结构,用链表作为底层结构的话,很容易实现这些功能。

「单调队列」的核心思路和「单调栈」类似。单调队列的 push 方法依然在队尾添加元素,但是要把前面比新元素小的元素都删掉:

1
2
3
4
5
6
7
8
9
10
11
class MonotonicQueue{
private:
deque<int> data;
public:
void push(int n){
while(!data.empty()&& data.back()< n)
data.pop_back();
data.push_back(n);
}
};

你可以想象,加入数字的大小代表人的体重,把前面体重不足的都压扁了,直到遇到更大的量级才停住

20210809212959

如果每个元素被加入时都这样操作,最终单调队列中的元素大小就会保持一个单调递减的顺序,因此我们的 max() API 可以可以这样写:

1
2
3
int max(){
return data.front();
}

pop() API 在队头删除元素 n,也很好写:

1
2
3
4
void pop(int n){
if(!data.empty()&& data.front()== n)
data.pop_front();
}

之所以要判断 data.front() == n,是因为我们想删除的队头元素 n 可能已经被「压扁」了,这时候就不用删除了:
20210809213911

至此,单调队列设计完毕,看下完整的解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
classMonotonicQueue{
private:
deque<int> data;
public:
void push(int n){
while(!data.empty()&& data.back()< n)
data.pop_back();
data.push_back(n);
}
int max(){return data.front();}
void pop(int n){
if(!data.empty()&& data.front()== n)
data.pop_front();
}
};
vector<int> maxSlidingWindow(vector<int>& nums,int k){
MonotonicQueue window;
vector<int> res;
for(int i =0; i < nums.size(); i++){
if(i < k -1){//先填满窗口的前 k - 1
window.push(nums[i]);
}else{// 窗口向前滑动
window.push(nums[i]);
res.push_back(window.max());
window.pop(nums[i - k +1]);
}
}
return res;
}

总结

单调队列在添加元素的时候靠删除元素保持队列的单调性

时间复杂度

读者可能疑惑,push 操作中含有 while 循环,时间复杂度不是 O(1) 呀,那么本算法的时间复杂度应该不是线性时间吧?

单独看 push 操作的复杂度确实不是 O(1),但是算法整体的复杂度依然是 O(N) 线性时间。要这样想,nums 中的每个元素最多被 push_back 和 pop_back 一次,没有任何多余操作,所以整体的复杂度还是 O(N)。

空间复杂度就很简单了,就是窗口的大小 O(k)。

题目

LeetCode-滑动窗口的最大值

模板

1
2
3
4
5
6
7
8
9
10
11
12
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
vector<int> res;
int q[nums.size()], hh=0, tt=-1;
memset(q, 0, sizeof q);
for(int i=0; i<nums.size(); i++){
if(hh<=tt && q[hh]<=i-k) hh ++;
while(hh<=tt && nums[q[tt]] <= nums[i]) tt--;
q[++ tt] = i;
if(i>=k-1) res.push_back(nums[q[hh]]);
}
return res;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
# include <iostream>
using namespace std;
const int N = 1000010;
int a[N], q[N], hh, tt = -1;

int main()
{
int n, k;
cin >> n >> k;
for (int i = 0; i < n; ++ i)
{
scanf("%d", &a[i]);
if (i - k + 1 > q[hh]) ++ hh; // 若队首出窗口,hh加1
while (hh <= tt && a[i] <= a[q[tt]]) -- tt; // 若队尾不单调,tt减1
q[++ tt] = i; // 下标加到队尾
if (i + 1 >= k) printf("%d ", a[q[hh]]); // 输出结果
}
cout << endl;
hh = 0; tt = -1; // 重置!
for (int i = 0; i < n; ++ i)
{
if (i - k + 1 > q[hh]) ++ hh;
while (hh <= tt && a[i] >= a[q[tt]]) -- tt;
q[++ tt] = i;
if (i + 1 >= k) printf("%d ", a[q[hh]]);
}
return 0;
}
//----

#include<iostream>
using namespace std;
const int N = 1e6 + 10;
int n, k, q[N], a[N];//q[N]存的是数组下标
int main()
{
int tt = -1, hh=0;//hh队列头 tt队列尾
cin.tie(0);
ios::sync_with_stdio(false);
cin>>n>>k;
for(int i = 0; i <n; i ++) cin>>a[i];
for(int i = 0; i < n; i ++)
{
//维持滑动窗口的大小
//当队列不为空(hh <= tt) 且 当当前滑动窗口的大小(i - q[hh] + 1)>我们设定的
//滑动窗口的大小(k),队列弹出队列头元素以维持滑动窗口的大小
if(hh <= tt && k < i - q[hh] + 1) hh ++;
//构造单调递增队列
//当队列不为空(hh <= tt) 且 当队列队尾元素>=当前元素(a[i])时,那么队尾元素
//就一定不是当前窗口最小值,删去队尾元素,加入当前元素(q[ ++ tt] = i)
while(hh <= tt && a[q[tt]] >= a[i]) tt --;
q[ ++ tt] = i;
if(i + 1 >= k) printf("%d ", a[q[hh]]);
}
puts("");
hh = 0,tt = -1;
for(int i = 0; i < n; i ++)
{
if(hh <= tt && k < i - q[hh] + 1) hh ++;
while(hh <= tt && a[q[tt]] <= a[i]) tt --;
q[ ++ tt] = i;
if(i + 1 >= k ) printf("%d ", a[q[hh]]);
}
return 0;
}



单调栈

单调栈实际上就是,只是利用了一些巧妙的逻辑,使得每次新元素入栈后,栈内的元素都保持有序(单调递增或单调递减)。

单调栈用途不太广泛,只处理一种典型的问题,叫做 Next Greater Element。本文用讲解单调队列的算法模版解决这类问题,并且探讨处理「循环数组」的策略。

首先,讲解 Next Greater Number 的原始问题:给你一个数组,返回一个等长的数组,对应索引存储下一个更大元素,如果没有更大的元素,就存 -1。不好用语言解释清楚,直接上一个例子:

给你一个数组 [2,1,2,4,3],你返回数组 [4,2,4,-1,-1]

解释:第一个 2 后面比 2 大的数是 4; 1 后面比 1 大的数是 2;第二个 2 后面比 2 大的数是 4; 4 后面没有比 4 大的数,填 -1;3 后面没有比 3 大的数,填 -1。

这道题的暴力解法很好想到,就是对每个元素后面都进行扫描,找到第一个更大的元素就行了。但是暴力解法的时间复杂度是 O($n^2$)

这个问题可以这样抽象思考:把数组的元素想象成并列站立的人,元素大小想象成人的身高。这些人面对你站成一列,如何求元素「2」的 Next Greater Number 呢?很简单,如果能够看到元素「2」,那么他后面可见的第一个人就是「2」的 Next Greater Number,因为比「2」小的元素身高不够,都被「2」挡住了,第一个露出来的就是答案。

20210811102755

这个情景很好理解吧?带着这个抽象的情景,先来看下代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
vector<int> nextGreaterElement(vector<int>& nums) {
vector<int> ans(nums.size()); // 存放答案的数组
stack<int> s;
for (int i = nums.size() - 1; i >= 0; i--) { // 倒着往栈里放
while (!s.empty() && s.top() <= nums[i]) { // 判定个子高矮

s.pop(); // 矮个起开,反正也被挡着了。。。
}

ans[i] = s.empty() ? -1 : s.top(); // 这个元素身后的第一个高个

s.push(nums[i]); // 进队,接受之后的身高判定吧!
}
return ans;
}

这就是单调队列解决问题的模板。for 循环要从后往前扫描元素,因为我们借助的是栈的结构,倒着入栈,其实是正着出栈。while 循环是把两个“高个”元素之间的元素排除,因为他们的存在没有意义,前面挡着个“更高”的元素,所以他们不可能被作为后续进来的元素的 Next Great Number 了。

这个算法的时间复杂度不是那么直观,如果你看到 for 循环嵌套 while 循环,可能认为这个算法的复杂度也是 O(n^2),但是实际上这个算法的复杂度只有 O(n)。

分析它的时间复杂度,要从整体来看:总共有 n 个元素,每个元素都被 push 入栈了一次,而最多会被 pop 一次,没有任何冗余操作。所以总的计算规模是和元素规模 n 成正比的,也就是 O(n) 的复杂度。

现在,你已经掌握了单调栈的使用技巧,来一个简单的变形来加深一下理解。

给你一个数组 T = [73, 74, 75, 71, 69, 72, 76, 73],这个数组存放的是近几天的天气气温(这气温是铁板烧?不是的,这里用的华氏度)。你返回一个数组,计算:对于每一天,你还要至少等多少天才能等到一个更暖和的气温;如果等不到那一天,填 0 。

举例:给你 T = [73, 74, 75, 71, 69, 72, 76, 73],你返回 [1, 1, 4, 2, 1, 1, 0, 0]。

解释:第一天 73 华氏度,第二天 74 华氏度,比 73 大,所以对于第一天,只要等一天就能等到一个更暖和的气温。后面的同理。

你已经对 Next Greater Number 类型问题有些敏感了,这个问题本质上也是找 Next Greater Number,只不过现在不是问你 Next Greater Number 是多少,而是问你当前距离 Next Greater Number 的距离而已。

相同类型的问题,相同的思路,直接调用单调栈的算法模板,稍作改动就可以啦,直接上代码把。

1
2
3
4
5
6
7
8
9
10
11
12
13
vector<int> dailyTemperatures(vector<int>& T) {
vector<int> ans(T.size());
stack<int> s; // 这里放元素索引,而不是元素
for (int i = T.size() - 1; i >= 0; i--) {
while (!s.empty() && T[s.top()] <= T[i]) {
s.pop();
}
ans[i] = s.empty() ? 0 : (s.top() - i); // 得到索引间距
s.push(i); // 加入索引,而不是元素
}
return ans;
}

单调栈讲解完毕。下面开始另一个重点:如何处理「循环数组」

同样是 Next Greater Number,现在假设给你的数组是个环形的,如何处理?

给你一个数组 [2,1,2,4,3],你返回数组 [4,2,4,-1,4]。拥有了环形属性,最后一个元素 3 绕了一圈后找到了比自己大的元素 4 。

20210811105745

首先,计算机的内存都是线性的,没有真正意义上的环形数组,但是我们可以模拟出环形数组的效果,一般是通过 % 运算符求模(余数),获得环形特效:

1
2
3
4
5
6
7
int[] arr = {1,2,3,4,5};
int n = arr.length, index = 0;
while (true) {
print(arr[index % n]);
index++;
}

回到 Next Greater Number 的问题,增加了环形属性后,问题的难点在于:这个 Next 的意义不仅仅是当前元素的右边了,有可能出现在当前元素的左边(如上例)。

明确问题,问题就已经解决了一半了。我们可以考虑这样的思路:将原始数组“翻倍”,就是在后面再接一个原始数组,这样的话,按照之前“比身高”的流程,每个元素不仅可以比较自己右边的元素,而且也可以和左边的元素比较了。

20210811110157

怎么实现呢?你当然可以把这个双倍长度的数组构造出来,然后套用算法模板。但是,我们可以不用构造新数组,而是利用循环数组的技巧来模拟。直接看代码吧:

1
2
3
4
5
6
7
8
9
10
11
12
13
vector<int> nextGreaterElements(vector<int>& nums) {
int n = nums.size();
vector<int> res(n); // 存放结果
stack<int> s;
// 假装这个数组长度翻倍了
for (int i = 2 * n - 1; i >= 0; i--) {
while (!s.empty() && s.top() <= nums[i % n])
s.pop();
res[i % n] = s.empty() ? -1 : s.top();
s.push(nums[i % n]);
}
return res;
}

并查集

将两个集合合并–》例如连通分支合并一个

询问两个元素是否在一个集合当中

近乎O(1)

简单理解(转载)

为了解释并查集的原理,我将举一个更有爱的例子。 话说江湖上散落着各式各样的大侠,有上千个之多。他们没有什么正当职业,整天背着剑在外面走来走去,碰到和自己不是一路人的,就免不了要打一架。但大侠们有一个优点就是讲义气,绝对不打自己的朋友。而且他们信奉“朋友的朋友就是我的朋友”,只要是能通过朋友关系串联起来的,不管拐了多少个弯,都认为是自己人。这样一来,江湖上就形成了一个一个的群落,通过两两之间的朋友关系串联起来。而不在同一个群落的人,无论如何都无法通过朋友关系连起来,于是就可以放心往死了打。但是两个原本互不相识的人,如何判断是否属于一个朋友圈呢?

我们可以在每个朋友圈内推举出一个比较有名望的人,作为该圈子的代表人物,这样,每个圈子就可以这样命名“齐达内朋友之队”“罗纳尔多朋友之队”……两人只要互相对一下自己的队长是不是同一个人,就可以确定敌友关系了。

但是还有问题啊,大侠们只知道自己直接的朋友是谁,很多人压根就不认识队长,要判断自己的队长是谁,只能漫无目的的通过朋友的朋友关系问下去:“你是不是队长?你是不是队长?”这样一来,队长面子上挂不住了,而且效率太低,还有可能陷入无限循环中。于是队长下令,重新组队。队内所有人实行分等级制度,形成树状结构,我队长就是根节点,下面分别是二级队员、三级队员。每个人只要记住自己的上级是谁就行了。遇到判断敌友的时候,只要一层层向上问,直到最高层,就可以在短时间内确定队长是谁了。由于我们关心的只是两个人之间是否连通,至于他们是如何连通的,以及每个圈子内部的结构是怎样的,甚至队长是谁,并不重要。所以我们可以放任队长随意重新组队,只要不搞错敌友关系就好了。于是,门派产生了。

20210803124721

下面我们来看并查集的实现。 int pre[1000]; 这个数组,记录了每个大侠的上级是谁。大侠们从1或者0开始编号(依据题意而定),pre[15]=3就表示15号大侠的上级是3号大侠。如果一个人的上级就是他自己,那说明他就是掌门人了,查找到此为止。也有孤家寡人自成一派的,比如欧阳锋,那么他的上级就是他自己。每个人都只认自己的上级。比如胡青牛同学只知道自己的上级是杨左使。张无忌是谁?不认识!要想知道自己的掌门是谁,只能一级级查上去。 find这个函数就是找掌门用的,意义再清楚不过了(路径压缩算法先不论,后面再说)。

1
2
3
4
5
6
7
int find(int x)                    //查找我(x)的掌门
{
int r=x; //委托 r 去找掌门
while (pre[r ]!=r) //如果r的上级不是r自己(也就是说找到的大侠他不是掌门 = =)
r=pre[r ] ; // r 就接着找他的上级,直到找到掌门为止。
return r ; //掌门驾到~~~
}

再来看看路径压缩算法。建立门派的过程是用join函数两个人两个人地连接起来的,谁当谁的手下完全随机。最后的树状结构会变成什么胎唇样,我也完全无法预计,一字长蛇阵也有可能。这样查找的效率就会比较低下。最理想的情况就是所有人的直接上级都是掌门,一共就两级结构,只要找一次就找到掌门了。哪怕不能完全做到,也最好尽量接近。这样就产生了路径压缩算法。 设想这样一个场景:两个互不相识的大侠碰面了,想知道能不能揍。 于是赶紧打电话问自己的上级:“你是不是掌门?” 上级说:“我不是呀,我的上级是谁谁谁,你问问他看看。” 一路问下去,原来两人的最终boss都是东厂曹公公。 “哎呀呀,原来是记己人,西礼西礼,在下三营六组白面葫芦娃!” “幸会幸会,在下九营十八组仙子狗尾巴花!” 两人高高兴兴地手拉手喝酒去了。 “等等等等,两位同学请留步,还有事情没完成呢!”我叫住他俩。 “哦,对了,还要做路径压缩。”两人醒悟。 白面葫芦娃打电话给他的上级六组长:“组长啊,我查过了,其习偶们的掌门是曹公公。不如偶们一起及接拜在曹公公手下吧,省得级别太低,以后查找掌门麻环。” “唔,有道理。” 白面葫芦娃接着打电话给刚才拜访过的三营长……仙子狗尾巴花也做了同样的事情。 这样,查询中所有涉及到的人物都聚集在曹公公的直接领导下。每次查询都做了优化处理,所以整个门派树的层数都会维持在比较低的水平上。路径压缩的代码,看得懂很好,看不懂也没关系,直接抄上用就行了。总之它所实现的功能就是这么个意思。

20210803124845

acwing模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
原模板:

int find (int x)
{
if(x != p[x]) p[x] = find(p[x]);
return p[x];
}
可以把y总的模板拆分一下,会方便理解些

int find (int x)
{
if(x != p[x])
{
int t = find(p[x]); //寻找根结点,找到后回溯
p[x] = t; //路径压缩
}
return p[x];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

#include<iostream>

using namespace std;

const int N=100010;
int p[N];//定义多个集合

int find(int x)
{
if(p[x]!=x) p[x]=find(p[x]);
/*
经上述可以发现,每个集合中只有祖宗节点的p[x]值等于他自己,即:
p[x]=x;
*/
return p[x];
//找到了便返回祖宗节点的值
}

int main()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) p[i]=i;
while(m--)
{
char op[2];
int a,b;
scanf("%s%d%d",op,&a,&b);
if(*op=='M') p[find(a)]=find(b);//集合合并操作
else
if(find(a)==find(b))
//如果祖宗节点一样,就输出yes
printf("Yes\n");
else
printf("No\n");
}
return 0;
}

快速排序

方法思想:分治法

将Array[l—r]分为Array[l-x]和Arrar[x-r](l和r为左右边界)

  • 左边的数组全部小于等于x
  • 右边的数组全部大于等于x
  • x只是一个参考值,随意

模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void quick_sort(int q[], int l, int r)
{
//递归的终止情况
if(l >= r) return;
//第一步:分成子问题
int i = l - 1, j = r + 1, x = q[l + r >> 1];
while(i < j)
{
do i++; while(q[i] < x);
do j--; while(q[j] > x);
if(i < j) swap(q[i], q[j]);
}
//第二步:递归处理子问题
quick_sort(q, l, j), quick_sort(q, j + 1, r);
//l---j -x- i---r
//第三步:子问题合并.快排这一步不需要操作,但归并排序的核心在这一步骤
}


题目

最小K个数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
vector<int> getLeastNumbers(vector<int>& arr, int k) {
quick_sorr(arr,0,arr.size()-1);
vector<int> temp;
temp.assign(arr.begin(),arr.begin()+k);
return temp;
}
private:
void quick_sorr(vector<int>& arr,int l,int r){
if(l>=r) return;
int i=l-1,j=r+1,x=arr[(l + r) >> 1];
while(i<j){
do i++;while(arr[i]<x);
do j--;while(x<arr[j]);
if(i<j) swap(arr[i],arr[j]);
}
quick_sorr(arr,l,j),quick_sorr(arr,j+1,r);
}
};

最接近原点的K个点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
vector<vector<int>> kClosest(vector<vector<int>>& points, int k) {
quick_sorr(points,0,points.size()-1);

return {points.begin(),points.begin()+k};
}

private:
void quick_sorr(vector<vector<int>>& a, int l,int r){
if(l >= r) return ;

int i = l - 1,j = r + 1;
int sum = a[(l + r) >> 1][0]*a[(l + r) >> 1][0]+a[(l + r) >> 1][1]*a[(l + r) >> 1][1];
while(i < j){
do i++; while(a[i][0] * a[i][0] + a[i][1] * a[i][1] < sum);
do j--; while(a[j][0] * a[j][0] + a[j][1] * a[j][1] > sum);
if(i < j) swap(a[i],a[j]);
}

quick_sorr(a,l,j);
quick_sorr(a,j+1,r);
}
};

VIP_Canceler V1.4.1

1. 更新日志:

  • 更新Fake Location[1.3.0.2]

1.3之前的版本将不在适配

  • 减小了内存占用

2. 支持软件:

阅读全文 »

1. 下载PicGo插件

20210722205519

先在扩展商店中下载PicGo插件(别告诉我你连VS code都没有)

2. 选择搭建图床的网站

目前picgo只支持weibo, qiniu, tcyun, upyun, github, aliyun, imgur 和 smms这几种,不支持gitee

这里我选择用GitHub做演示

如果你用其他的网站,方法也都是差不多的

阅读全文 »