一、单调栈

单调栈（Monotonic Stack）是一种特殊的栈结构，其核心思想是维护栈内元素的单调性（单调递增或单调递减）。单调栈通常用于解决与元素大小关系相关的问题，例如：

1. 找到数组中每个元素的下一个更大（或更小）元素。

2. 计算数组中每个元素左边或右边的第一个更大（或更小）元素。

3. 解决与区间最值相关的问题（如最大矩形面积）。

二、特点

1. 单调性：栈内元素始终保持单调递增或单调递减。

2. 操作规则：

   如果新元素满足单调性，直接压入栈。

如果新元素破坏了单调性，则弹出栈顶元素，直到满足单调性为止。

3. 时间复杂度：由于每个元素最多入栈和出栈一次，因此时间复杂度通常为O(n)

三、应用场景

1. 下一个更大元素：
   
   给定一个数组，找到每个元素的下一个更大元素。

2. 每日温度：
   
   给定一个温度数组，计算每天需要等待多少天才能遇到更高的温度。

3. 最大矩形面积：
   
   给定一个柱状图，计算其中最大的矩形面积。

4. 滑动窗口最大值：
   
   在滑动窗口中快速找到最大值。

四、步骤

以找到数组中每个元素的下一个更大元素为例：

1. 初始化：创建一个空栈和一个结果数组。

2. 遍历数组：

• 如果当前元素大于栈顶元素，则栈顶元素的下一个更大元素就是当前元素。

• 弹出栈顶元素，并更新结果数组。

• 重复上述过程，直到当前元素小于等于栈顶元素或栈为空。

• 将当前元素压入栈。

3. 处理剩余元素：遍历结束后，栈中剩余的元素没有下一个更大元素，将其结果设置为 -1。

一、定义

滑动窗口算法（Sliding Window Algorithm）是一种用于解决数组或字符串中子数组或子串问题的优化技术。它通过维护一个窗口（通常是数组或字符串的一个连续子区间），在遍历过程中动态调整窗口的起始和结束位置，从而高效地解决问题。

滑动窗口的核心思想是：

• 窗口大小固定：窗口的大小在滑动过程中保持不变。

• 窗口大小可变：窗口的大小根据条件动态调整。

二、使用场景

滑动窗口算法通常用于以下场景：

1. 1.子数组/子串问题：

• 求满足条件的最大或最小子数组/子串。

• 例如：最大子数组和、最小覆盖子串、最长无重复字符子串等。

2. 2.固定窗口大小问题：

• 例如：计算大小为 k 的子数组的平均值。

3. 3.优化暴力解法：

• 将时间复杂度从 O(n²) 优化到 O(n)。

三、示例

1.例题1：固定窗口大小

【题目描述】给定一个数组和一个整数 k，计算所有大小为 k 的子数组的平均值。

【题目分析】

（1） 什么是子数组？

• 子数组是数组中连续的一段元素。

• 例如，数组 [1, 3, 2, 6, -1] 的子数组包括 [1, 3, 2]、[3, 2, 6] 等。

（2）什么是大小为 k 的子数组？

• 大小为 k 的子数组是指长度为 k 的连续子数组。

• 例如，如果 k = 3，那么子数组的长度必须是 3。

（3）什么是子数组的平均值？

• 子数组的平均值是指子数组中所有元素的和除以子数组的长度。

• 例如，子数组 [1, 3, 2] 的平均值是 (1 + 3 + 2) / 3 = 2。

（4）问题的目标

• 对于数组中的每一个大小为 k 的子数组，计算其平均值，并返回所有平均值的集合。

【解题思路】

（1）暴力解法

• 遍历数组，对于每一个起始位置 i，计算从 i 到 i + k - 1 的子数组的和，然后除以 k 得到平均值。

• 时间复杂度：O(n * k)，其中 n 是数组的长度。

（2）滑动窗口优化

• 使用滑动窗口技术，避免重复计算子数组的和。

• 初始化第一个窗口的和，然后在滑动窗口时，加上新元素，减去旧元素。

• 时间复杂度：O(n)。

#include <iostream>  using namespace std;  void sw(int nums[], int n, int k) {      if (n < k) return; // 如果数组长度小于k，直接返回      double windowSum = 0;      // 初始化窗口      for (int i = 0; i < k; i++) {          windowSum += nums[i];      }      cout << windowSum / k << " ";      // 滑动窗口      for (int i = k; i < n; i++) {          windowSum += nums[i] - nums[i - k]; // 加上新元素，减去旧元素          cout << windowSum / k << " ";      }      cout << endl;  }    int main() {      int nums[] = {1, 3, 2, 6, -1, 4, 1, 8, 2};      int n = sizeof(nums) / sizeof(nums[0]);      int k = 5;      sw(nums, n, k);      return 0;  }

【过程解释】

1. 初始化窗口：

• 计算第一个窗口的和 windowSum，即 nums[0] 到 nums[k-1] 的和。

• 输出第一个窗口的平均值 windowSum / k。

2. 滑动窗口：

• 从第 k 个元素开始，滑动窗口。

• 每次滑动时，加上新元素 nums[i]，减去旧元素 nums[i - k]。

• 输出当前窗口的平均值 windowSum / k。

图示：

第一次：（1+3+2）/3 

第二次：(3+2+6)/3 ，对比上一次，少了第一个数1，多了后一个数6

第二次：(2+6-1)/3 ，对比上一次，少了上一个数2，多了后一个数-1

一、差分：一维数组的差分可看作是一维数组前缀和的逆运算。

二、差分数组

首先给定一个原数组a:   a[1]、a[2]、a[3]、......

然后构造一个数组b: b[1]、b[2]、b[3]....

使得a[i]=b[1]+b[2]+b[3]+b[4]+.....b[i]。

那么根据上一节讲的，a数组就是b数组的前缀和数组。 

也就是说，a数组就是b数组的前缀和数组，反过来，我们把b数组叫做a数组的差分数组。话句话说，每一个a[i]数组都是b数组中从头开始的一段区间和。

三、功能及作用

    给区间[L,R]中每个数加上 c:  B[L] +=c， B[R+1] -=c

四、构造

考虑如何构造差分数组b：

最为直接的方法：

a[0]=0  b[1]=a[1]-a[0];  b[2]=a[2]-a[1];  b[3]=a[3]-a[2];  ......  b[n]=a[n]-a[n-1];

五、应用

【问题描述】给定区间[L,R]，让我们把a数组中的[L,R]区间中的每一个数都加上c， 即a[L]+c,  a[L+1]+c,  a[L+2]=c , ....  a[R]+c

解法一：暴力解法

用for循环，从L到R区间，时间复杂度O（n），如果我们需要对原数组执行m次这样的操作，那么时间复杂度就会变成O(n*m)。

解法二：差分

始终要记住一点：a数组是b数组的前缀和数组。比如对b数组的b[i]的修改，会影响到a数组中从a[i]及往后的每一个数。

首先让差分b数组中的b[L]+c，通过前缀和运算，a数组变成a[L]+c,... a[L+1]+c,.... a[n]+c

然后我们打个补丁， b[R+1] -c ，通过前缀和运算， a数组变成 a[R+1]-c,  ...  a[R+2]-c, ...   a[n] -c, ...

图解过程：

b[L]+c, 效果使得a数组中a[L]及以后的数都加上了c(红色部分)，但是我们只要求L到R区间加上c，因此还需要执行b[R+1]-c， 让a数组中a[R+1]以及往后的区间再减去c(绿色部分)，这样对于a[r]以后区间的数组相当于没有发生改变。

结论：给a数组中的[L,R]区间中的每一个数加上c。只需要对差分数组b做b[L]+=c，b[R+]-=c，时间复杂度为O（1）。

如果上面的描述不够清楚，我们可以借助下面方式来表示，我们假设a数组是原始数组，b数组是差分数组。我们的目的是让a数组的某个区间段加上一个数c。初始状态如下：

需求1：我们要将[1,4]范围内所有的数都加上3

规律：当对一个区间进行增减某个值的时候，他的差分数组对应的区间左端点的值会同步变化，而他的右端点的后一个值则会相反地变化。

那么用代码表示：

while(t--){//操作次数  	cin>>x>>y>>change;//左右端点值   	cin>>c;//c是每次加减的值   	b[x]=b[x]+c;  	b[y+1]=b[y+1]-c;  }

那么能不能反过来求a[i]呢，因为b数组是差分数组，满足公式b[i]=a[i]-a[i-1]

那么a[i]=a[i-1]+b[i]

六、题目

【题目描述】

输入一个长度为n的整数序列。

接下来输入m个操作，每个操作包含三个整数l, r, c，表示将序列中[l, r]之间的每个数加上c。

请你输出进行完所有操作后的序列。

【输入描述】

第一行包含两个整数n和m。

第二行包含n个整数，表示整数序列。

接下来m行，每行包含三个整数l，r，c，表示一个操作。

【输出描述】

共一行，包含n个整数，表示最终序列。

【样例输入】

6 3  1 2 2 1 2 1  1 3 1  3 5 1  1 6 1

【样例输出】

3 4 5 3 4 2

【数据范围】

1≤n,m≤100000,

1≤l≤r≤n,

−1000≤c≤1000,

−1000≤整数序列中元素的值≤1000

0.前言   

     二叉树（Binary Tree）的递归定义如下：二叉树要么为空，要么由根结点（root）、左子树（left subtree）和右子树（right subtree）组成，而左子树和右子树分别是一棵二叉树。

    树（tree）和二叉树类似，区别在于每个结点不一定只有两棵子树。比如树的目录，根结点有12棵子树：第1章，第2章，第3章，。。。、第12章，而第一章又有5棵子树：1.1，1.2，1.3，。。。1.5。

1.二叉树的编号

    【例题】6-6 小球下落

    【题目描述】

     有一棵二叉树，最大深度为D，且所有叶子的深度都相同。所有结点从上到下从左到右编号为1，2，3，。。。，2D-1。在结点1处放一个小球，它会往下落。每个内结点上都有一个开关，初始全部关闭。每当有小球落在一个开关上时，状态都会改变。当小球到达一个内结点时，如果该结点上的开关关闭，则往左走，否则往右走，直到走到叶子结点。如下图所示

一个小球从结点1开始依次下落，最后一个小球将会落在哪里？输入叶子深度D和小球个数I，输出第I个小球最后所在的叶子编号。假设I不超过整棵树的叶子个数。D<=20。输入最多包含1000组数据。

【样例输入1】

4 2  3 4  10 1  2 2  8 128  16 12345

【样例输出1】

12  7  512  3  255  36358

【题目描述】

给出一个长度位n的序列a,选出其中连续且非空的一段使得这段和最大

【输入描述】

第一行是一个整数，表示序列的长度n。

第二行有n个整数，第i个整数表示序列的第i个数字ai

【输出描述】

输出一行一个整数表示答案。

【样例输入】

7  2 -4 3 -1 2 -4 3

【样例输出】

4