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;
}

题解:

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

具体步骤

初始化：
- 创建一个栈，用来存储柱子的下标，初始时栈是空的。
- 准备一个变量 ans，用来记录最终接住的雨水量，初始值为 0。
遍历柱子数组：
- 对于数组中的每个柱子：
  - 当栈不为空，并且当前柱子的高度大于栈顶柱子的高度时：
    - 把栈顶元素弹出，得到这个柱子的下标。
    - 如果弹出栈顶元素后栈为空了，说明没有左边界，没办法接住雨水，就停止计算这一轮。
    - 取出新的栈顶元素下标，作为左边界。
    - 计算当前柱子和左边界柱子之间的距离。
    - 计算能接住雨水的高度，也就是左右边界柱子高度的较小值减去弹出柱子的高度。
    - 用距离乘以高度，得到这部分的雨水量，累加到 ans 中。
  - 把当前柱子的下标放入栈中。
返回结果：遍历完所有柱子后，ans 就是最终能接住的雨水量。

复杂度分析

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

题目二：滑动窗口最大值

题目描述：给定一个数组 nums 和一个整数 k，请找出所有长度为 k 的滑动窗口中的最大值。
示例：输入 nums = [1,3,-1,-3,5,3,6,7]，k = 3，输出 [3,3,5,5,6,7]。
思路：可以使用单调队列来解决。单调队列是一种特殊的数据结构，它可以在的时间内获取队列中的最大值或最小值。在遍历数组时，维护一个单调递减的队列，队列中存储数组的下标。当窗口移动时，判断队首元素是否在当前窗口内，如果不在则弹出队首元素，每次将当前窗口的最大值加入结果列表。

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;
}

题解：

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

具体步骤

特殊情况处理：
- 如果数组为空或者窗口大小为 0，直接返回空结果。
初始化：
- 计算结果数组的长度，它等于数组长度减去窗口大小再加 1。
- 动态分配结果数组的内存。
- 创建一个队列，用来存储元素的下标，同时设置队首和队尾指针。
遍历数组：
- 对于数组中的每个元素：
  - 先检查队首元素是否还在当前窗口内，如果不在，就把队首元素移除。
  - 然后维护队列的单调性，把队列中比当前元素小的元素都移除。
  - 把当前元素的下标放入队列。
  - 当窗口大小达到 k 时，队首元素对应的就是当前窗口的最大值，把这个值记录到结果数组中。
返回结果：遍历完数组后，结果数组里就存储了所有滑动窗口的最大值。