2.14日学习总结

题目一：接雨水问题

1.题目描述：给定一个数组 height 表示一个地形的高度图，数组中的每个元素代表每个宽度为 1 的柱子的高度。计算按此排列的柱子，下雨之后能接多少雨水。

2.示例：输入 height = [0,1,0,2,1,0,1,3,2,1,2,1]，输出 6。

3.思路：可以使用栈来解决。遍历数组，当栈为空或者当前高度小于等于栈顶元素高度时，将当前元素的索引入栈。当当前高度大于栈顶元素高度时，说明可以接雨水，不断弹出栈顶元素并计算接水量，直到栈为空或者当前高度小于等于栈顶元素高度。

AC代码：

#include <stdio.h>// 计算接雨水量的函数
int t(int* h, int s) {int st[s];int t = -1;int a = 0;for (int i = 0; i < s; i++) {while (t != -1 && h[i] > h[st[t]]) {int ti = st[t--];if (t == -1) {break;}int l = st[t];int d = i - l - 1;int bh = (h[l] < h[i] ? h[l] : h[i]) - h[ti];a += d * bh;}st[++t] = i;}return a;
}int main() {int h[] = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};int s = sizeof(h) / sizeof(h[0]);int r = t(h, s);printf("接雨水的量为: %d\n", r);return 0;
}

题解:

要计算每个位置能接住多少雨水，关键在于看它左右两边最高的柱子。一个位置能接住的雨水量，等于它左右两边最高柱子高度的较小值减去它自身的高度。让栈像一个容器，我们把柱子的下标按柱子高度从高到低的顺序依次放进去。当遇到一个比栈顶柱子高的柱子时，就说明可以计算栈顶柱子和当前柱子之间能接住的雨水量了。

具体步骤

1. 初始化：

   • 创建一个栈，用来存储柱子的下标，初始时栈是空的。
   • 准备一个变量 ans，用来记录最终接住的雨水量，初始值为 0。

2. 遍历柱子数组：

   • 对于数组中的每个柱子：
     • 当栈不为空，并且当前柱子的高度大于栈顶柱子的高度时：
       • 把栈顶元素弹出，得到这个柱子的下标。
       • 如果弹出栈顶元素后栈为空了，说明没有左边界，没办法接住雨水，就停止计算这一轮。
       • 取出新的栈顶元素下标，作为左边界。
       • 计算当前柱子和左边界柱子之间的距离。
       • 计算能接住雨水的高度，也就是左右边界柱子高度的较小值减去弹出柱子的高度。
       • 用距离乘以高度，得到这部分的雨水量，累加到 ans 中。
     • 把当前柱子的下标放入栈中。

3. 返回结果：遍历完所有柱子后，ans 就是最终能接住的雨水量。

复杂度分析

• 时间复杂度：每个柱子最多入栈和出栈一次，所以时间复杂度是 ，这里的  是柱子数组的长度。
• 空间复杂度：主要是栈的空间开销，最坏情况下栈需要存储所有柱子的下标，所以空间复杂度是 

 

题目二： 滑动窗口最大值

1. 题目描述：给定一个数组 nums 和一个整数 k，请找出所有长度为 k 的滑动窗口中的最大值。

2. 示例：输入 nums = [1,3,-1,-3,5,3,6,7]，k = 3，输出 [3,3,5,5,6,7]。

3. 思路：可以使用单调队列来解决。单调队列是一种特殊的数据结构，它可以在  的时间内获取队列中的最大值或最小值。在遍历数组时，维护一个单调递减的队列，队列中存储数组的下标。当窗口移动时，判断队首元素是否在当前窗口内，如果不在则弹出队首元素，每次将当前窗口的最大值加入结果列表。

AC代码：

#include <stdio.h>
#include <stdlib.h>// 计算滑动窗口最大值的函数
int* m(int* n, int ns, int k, int* rs) {if (ns == 0 || k == 0) {*rs = 0;return NULL;}*rs = ns - k + 1;int* r = (int*)malloc(sizeof(int) * (*rs));int q[ns];int f = 0, e = -1;for (int i = 0; i < ns; i++) {if (f <= e && q[f] <= i - k) {f++;}while (f <= e && n[q[e]] <= n[i]) {e--;}q[++e] = i;if (i >= k - 1) {r[i - k + 1] = n[q[f]];}}return r;
}int main() {int n[] = {1, 3, -1, -3, 5, 3, 6, 7};int ns = sizeof(n) / sizeof(n[0]);int k = 3;int rs;int* r = m(n, ns, k, &rs);printf("滑动窗口最大值为: ");for (int i = 0; i < rs; i++) {printf("%d ", r[i]);}printf("\n");free(r);return 0;
}

题解：

我们可以使用单调队列来解决这个问题。单调队列是一种特殊的队列，队列里的元素要么单调递增，要么单调递减。在本题中，我们用单调递减队列来维护窗口内的最大值。队列里存储的是元素的下标，队首元素对应的就是当前窗口中的最大值。

具体步骤

1. 特殊情况处理：

   • 如果数组为空或者窗口大小为 0，直接返回空结果。

2. 初始化：

   • 计算结果数组的长度，它等于数组长度减去窗口大小再加 1。

   • 动态分配结果数组的内存。

   • 创建一个队列，用来存储元素的下标，同时设置队首和队尾指针。

3. 遍历数组：

   • 对于数组中的每个元素：

     • 先检查队首元素是否还在当前窗口内，如果不在，就把队首元素移除。

     • 然后维护队列的单调性，把队列中比当前元素小的元素都移除。

     • 把当前元素的下标放入队列。

     • 当窗口大小达到 k 时，队首元素对应的就是当前窗口的最大值，把这个值记录到结果数组中。

4. 返回结果：遍历完数组后，结果数组里就存储了所有滑动窗口的最大值。

复杂度分析

• 时间复杂度：每个元素最多入队和出队一次，所以时间复杂度是 ，其中  是数组的长度。

• 空间复杂度：队列中最多存储  个元素，所以空间复杂度是 。