第1行包含两个正整数N，M，表示了数列A[i]的长度与每段和的最大值；
第2行包含N个空格隔开的非负整数A[i]，如题目所述。
5 6 4 2 4 5 1
3
【数据范围】
对于20%的数据，有N≤10；
对于40%的数据，有N≤1000；
对于100%的数据，有N≤100000，M≤109，M大于所有数的最小值，A[i]之和不超过109。
3 0 2 2 4 1 3
2
【数据规模】
对于20%的数据，n≤10。
对于50%的数据，n≤1000。
对于70%的数据，n≤100000。
对于20%的数据，n≤1000000,0≤ai<bi≤1000000。
第一行一个正整数n≤1000000，表示小朋友的个数．
接下来n行，每行一个整数ai，表示第i个小朋友得到的糖果的颗数．
4 1 2 5 4
4
一、单调栈
单调栈（Monotonic Stack）是一种特殊的栈结构，其核心思想是维护栈内元素的单调性（单调递增或单调递减）。单调栈通常用于解决与元素大小关系相关的问题，例如：
找到数组中每个元素的下一个更大（或更小）元素。
计算数组中每个元素左边或右边的第一个更大（或更小）元素。
解决与区间最值相关的问题（如最大矩形面积）。
二、特点
单调性：栈内元素始终保持单调递增或单调递减。
操作规则：
如果新元素满足单调性，直接压入栈。
如果新元素破坏了单调性，则弹出栈顶元素，直到满足单调性为止。
时间复杂度：由于每个元素最多入栈和出栈一次，因此时间复杂度通常为O(n)
三、应用场景
下一个更大元素：
给定一个数组，找到每个元素的下一个更大元素。
每日温度：
给定一个温度数组，计算每天需要等待多少天才能遇到更高的温度。
最大矩形面积：
给定一个柱状图，计算其中最大的矩形面积。
滑动窗口最大值：
在滑动窗口中快速找到最大值。
四、步骤
以找到数组中每个元素的下一个更大元素为例：
初始化：创建一个空栈和一个结果数组。
遍历数组：
如果当前元素大于栈顶元素，则栈顶元素的下一个更大元素就是当前元素。
弹出栈顶元素，并更新结果数组。
重复上述过程，直到当前元素小于等于栈顶元素或栈为空。
将当前元素压入栈。
处理剩余元素：遍历结束后，栈中剩余的元素没有下一个更大元素，将其结果设置为 -1。
对于滑动窗口第二类：窗口大小可变类型
图解如下，类似双指针算法。
【解题思想】
1、字符串 S 中使用双指针的左右指针技巧，初始化 left = right = 0，把索引的左闭右开区间 [left,right) 称为一个「窗口」。
2、先不断增加 right 指针扩大窗口[left, right)（也就是 right++），直到窗口中的字符串符合要求：包含 T 中所有字符。
3、停止增加 right ，转而不断增加 left 指针缩小窗口[left, right)（也就是 left++），直到窗口中的字符串不再符合要求：不包含 T 中所有字符。
4、同时，每增加 left，都要更新一轮结果。
5、重复 2 & 3 步骤，直到 right 到达字符串 S 的尽头。
6、第 2 步骤寻找「可行解」（符合要求），第 3 步骤优化「可行解」（找最短），最终找到「最优解」（最短的覆盖子串）。
7、左右指针轮流前进，窗口大小增增减减，窗口不断向右滑动，这就是「滑动窗口」名字的来历。
一、定义
滑动窗口算法（Sliding Window Algorithm）是一种用于解决数组或字符串中子数组或子串问题的优化技术。它通过维护一个窗口（通常是数组或字符串的一个连续子区间），在遍历过程中动态调整窗口的起始和结束位置，从而高效地解决问题。
滑动窗口的核心思想是：
窗口大小固定：窗口的大小在滑动过程中保持不变。
窗口大小可变：窗口的大小根据条件动态调整。
二、使用场景
滑动窗口算法通常用于以下场景：
1.子数组/子串问题：
求满足条件的最大或最小子数组/子串。
例如：最大子数组和、最小覆盖子串、最长无重复字符子串等。
2.固定窗口大小问题：
例如：计算大小为 k 的子数组的平均值。
3.优化暴力解法：
将时间复杂度从 O(n²) 优化到 O(n)。
三、示例
1.例题1：固定窗口大小
【题目描述】给定一个数组和一个整数 k，计算所有大小为 k 的子数组的平均值。
【题目分析】
子数组是数组中连续的一段元素。
例如，数组 [1, 3, 2, 6, -1] 的子数组包括 [1, 3, 2]、[3, 2, 6] 等。
k 的子数组？大小为 k 的子数组是指长度为 k 的连续子数组。
例如，如果 k = 3，那么子数组的长度必须是 3。
子数组的平均值是指子数组中所有元素的和除以子数组的长度。
例如，子数组 [1, 3, 2] 的平均值是 (1 + 3 + 2) / 3 = 2。
对于数组中的每一个大小为 k 的子数组，计算其平均值，并返回所有平均值的集合。
【解题思路】
遍历数组，对于每一个起始位置 i，计算从 i 到 i + k - 1 的子数组的和，然后除以 k 得到平均值。
时间复杂度：O(n * k)，其中 n 是数组的长度。
使用滑动窗口技术，避免重复计算子数组的和。
初始化第一个窗口的和，然后在滑动窗口时，加上新元素，减去旧元素。
时间复杂度：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; }【过程解释】
初始化窗口：
计算第一个窗口的和 windowSum，即 nums[0] 到 nums[k-1] 的和。
输出第一个窗口的平均值 windowSum / k。
滑动窗口：
从第 k 个元素开始，滑动窗口。
每次滑动时，加上新元素 nums[i]，减去旧元素 nums[i - k]。
输出当前窗口的平均值 windowSum / k。
图示：
第一次：（1+3+2）/3
第二次：(3+2+6)/3 ，对比上一次，少了第一个数1，多了后一个数6
第二次：(2+6-1)/3 ，对比上一次，少了上一个数2，多了后一个数-1
【题目描述】
输入一个n×n的黑白图像（1表示黑色，0表示白色），任务是统计其中黑色连通块的个数。如果两个黑格子有公共边或者公共顶点，就说它们属于同一个联通块。如下图所示的图形有3个联通块。
【输入描述】
第1行输入一个正整数n（n≤700），此后输入n行，每行是由n个0或1组成的字符串。
【输出描述】
输出连通块的个数
【样例输入】
6 100100 001010 000000 110000 111000 010100
【样例输出】
3
【题目描述】
起点与终点相隔4500米。现Charley 需要从起点骑车到终点。但是，他有个习惯，沿途需要有人陪伴，即以相同的速度， 与另外一个人一起骑。而当他遇到以更快的速度骑车的人时，他会以相应的速度跟上这个更快的人。先给定所有与Charley 同路的人各自的速度与出发时间，问Charley 以这种方式跟人，骑完4500米需要多少时间。得出的结果若是小数，则向上取整。
【输入描述】
输入若干组数据，每组数据第一行n(1≤n≤10000),n为0，表示输入结束，接着输入n行数据，每行2个数据，表示速度v和出发时间t，如果t<0，表示陪伴人提早出发了。
【输出描述】
输出对应若干行数据，每行输出1个数，表示最快到达的时间。
【样例输入】
4 20 0 25 -155 27 190 30 240 2 21 0 22 34 0
【样例输出】
780 771
【题目描述】
一个迷宫由R行C列格子组成，有的格子里有障碍物，不能走；有的格子是空地，可以走。
给定一个迷宫，求从左上角走到右下角最少需要走多少步(数据保证一定能走到)。只能在水平方向或垂直方向走，不能斜着走。
【输入描述】
第一行是两个整数，R和C，代表迷宫的行数和列数。（ 1<= R，C <= 40)
接下来是R行，每行C个字符，代表整个迷宫。空地格子用’.‘表示，有障碍物的格子用’#‘表示。迷宫左上角和右下角都是’.’。
【输出描述】
输出从左上角走到右下角至少要经过多少步（即至少要经过多少个空地格子）。计算步数要包括起点和终点。
【样例输入】
5 5 ..### #.... #.#.# #.#.# #.#..
【样例输出】
9