一. 簡介
本文記錄力扣網上的邏輯編程題，涉及數組方面的，這里記錄一下 C語言實現和Python實現。
二.?力扣網C語言編程題：接雨水
題目：接雨水
給定?n 個非負整數表示每個寬度為 1 的柱子的高度圖，計算按此排列的柱子，下雨之后能接多少雨水。
示例 2：
輸入：height = [4,2,0,3,2,5]
輸出：9
提示：
? ? n == height.length
? ? 1 <= n <= 2 * 104
? ? 0 <= height[i] <= 105
初步思路：
暴力解法是最直觀的方法，它直接按照問題的定義來計算每個位置能夠接多少水。
從左到右遍歷數組元素，計算每個柱子的接水量，然后，不斷累加即可。但是問題的關鍵是如何計算每個柱子能接的雨水量？
通過柱型圖觀察可知，只有低洼的位置才會接到雨水。具體意思就是，某個元素 nums[i]的左側與右側所有元素只要高于其本身就可接到雨水。
核心原理：
雨水能被接住的條件是：左右兩側存在比當前位置更高的墻。
每個位置能接的雨水量 = min (左側最高墻高度，右側最高墻高度) - 當前墻高度（若結果為負則取 0，其中左側指的是某個元素的左側所有元素值最大的元素）。
解題思路一：（暴力解法）
暴力解法，從左向右邊遍歷數組元素，逐個依次計算每個元素所能接的雨水量，同時不斷累加即可。
遍歷數組，假如計算 nums[i]元素的接雨水量：
首先，計算 nums[i]左邊所有元素中值最大的元素，計算 nums[i]右邊所有元素中值最大的元素。
然后，使用公式計算 nums[i]能接到的雨水量：min(左邊最大元素值，右邊最大元素值)-nums[i]；
總結：n個元素都要進行一輪這樣的計算，時間復雜度為O(n*n)，空間復雜度為O(1)。這樣時間復雜度太高，超過時間限制，需要進行進一步優化以減少時間復雜度。
解題思路二：（動態規劃）
暴力解法中，每次要計算某個元素的左邊所有元素的最大值和右邊所有元素的最大值。可以用兩個數組，分別統計出來每個元素的左邊中值最大的元素與右邊中值最大的元素（也就是提前統計好），最后，統計所有元素的接水量。
具體方法：
1. 分配兩個數組left_buf，right_buf，分別統計每個元素的左邊中值最大的元素與右邊中值最大的元素；
2. 遍歷數組，統計每個元素左邊所有元素中最大值，并記錄到數組left_buf中（從左向右）；
3. 遍歷數組，統計每個元素右邊所有元素中最大值，并記錄到數組right_buf中（從右向右）；
4. 計算所有元素的接水量，left_buf數組與 right_buf數組對應比較，求對應位置最小值。使用公式計算每個位置上的接水量：min(left_buf[i]， right_buf[i]) - height[i]，并不斷累加。
C語言實現如下：
#include <stdio.h>
#include <stdlib.h>//動態規劃
int trap(int *height, int heightSize) {if((height == NULL) || (heightSize < 2)) {return 0;}int i = 0;int receive_water = 0;int* left_max = (int*)calloc(heightSize, sizeof(int));int* right_max = (int*)calloc(heightSize, sizeof(int));//統計所有元素左側的最大值left_max[0] = height[0];for(i = 1; i < heightSize; i++) {left_max[i] = fmax(left_max[i-1], height[i]);}//統計所有元素右側的最大值right_max[heightSize-1] = height[heightSize-1];for(i = heightSize-2; i >=0; i--) {right_max[i] = fmax(right_max[i+1], height[i]);}// 計算接的雨水量for(i = 1; i < (heightSize-1); i++) {receive_water += fmin(left_max[i], right_max[i]) - height[i];}free(left_max);left_max = NULL;free(right_max);right_max = NULL;return receive_water;
}
)
