leetcode刷题日记——接雨水

[ 题目描述 ]：

[ 思路 ]：

• 题目要求求凹进去的部分能接多少雨水，即有多少个格子
• 可以从第一个高度快出发去寻找下一个高于或者等于他的格子，然后计算其中的差值
  • 有高于或等于他的格子，计算他俩中间能装的雨水
  • 当后续没有高于他的格子时，去寻找下一个有高度的格子
    • 如果相邻，则左边下标变为这个有高度格子的下标
    • 不相邻，求雨水数量
  • 找到的格子作为新的参照，然后再进行新一轮的遍历，直至全部找完
• 突然想到如果没有高于他的格子，那是不是可以把他的高度削减一个，这样就不用判断下一个有高度的格子是否与他相邻
• 运行如下
• 时间复杂度为O(n*h)，h为高度，如果最高的高度与次高度相差很大，那么时间会很大。但证明了其主体思路没有问题

int calculate(int *height,int left,int right){int sum=0;for(int i=left+1;i<right;i++){sum+=height[left]-height[i];}return sum;
}int trap(int* height, int heightSize) {int left=0,right=0,sum=0;while(right<heightSize){if(height[left]>height[right]){right++;}else{sum+=calculate(height,left,right);left=right;right++;}if(right==heightSize && left!=heightSize-1){height[left]--;right=left+1;}}return sum;
}

• 最影响时间的就是指针回退，如果可以把指针回退删掉，那么时间复杂度就可以降到O(n)
• 雨水的分布呈山字性，中间雨水的高度永远高于或等于两边的雨水
• 雨水两边最低的墙决定了中间能存储多少雨水，那我们可以从两边向中间遍历，并记录两边的最大值，当遇见更大的值时进行更换，没遇见，则计算雨水
• 运行如下：

int trap(int* height, int heightSize) {int left=0,right=heightSize-1,sum=0,left_max=height[0],right_max=height[heightSize-1];while(right!=left){if(left_max<=right_max){left++;if(height[left]>left_max){left_max=height[left];}else{sum+=left_max-height[left];}}else{right--;if(height[right]>right_max){right_max=height[right];}else{sum+=right_max-height[right];}}}return sum;
}

• 时间复杂度O(n)，空间复杂度O(1)

[ 官方题解 ]：

• 一、动态规划，先记录每个柱子两边最高的柱子，然后从其中选择较低的柱子与其自身高度比较，较低柱子减去其自身高度就是存储的雨水量

int trap(int* height, int heightSize) {int n = heightSize;if (n == 0) {return 0;}int leftMax[n];memset(leftMax, 0, sizeof(leftMax));leftMax[0] = height[0];for (int i = 1; i < n; ++i) {leftMax[i] = fmax(leftMax[i - 1], height[i]);}int rightMax[n];memset(rightMax, 0, sizeof(rightMax));rightMax[n - 1] = height[n - 1];for (int i = n - 2; i >= 0; --i) {rightMax[i] = fmax(rightMax[i + 1], height[i]);}int ans = 0;for (int i = 0; i < n; ++i) {ans += fmin(leftMax[i], rightMax[i]) - height[i];}return ans;
}

• 二、单调栈，使用单调递减栈维护柱子的索引，确保栈中柱子高度从栈底到栈顶单调递减。
  • 遇到更高的柱子时出栈，计算形成的“凹槽”能存多少水，计算公式为：存水量=(右边界索引−左边界索引−1)×(min(左边界高度,右边界高度)−当前柱子高度)
  • 不断重复直到遍历完整个数组，最终累加所有可能的存水量。

int trap(int* height, int heightSize) {int n = heightSize;if (n == 0) {return 0;}int ans = 0;int stk[n], top = 0;for (int i = 0; i < n; ++i) {while (top && height[i] > height[stk[top - 1]]) {int stk_top = stk[--top];if (!top) {break;}int left = stk[top - 1];int currWidth = i - left - 1;int currHeight = fmin(height[left], height[i]) - height[stk_top];ans += currWidth * currHeight;}stk[top++] = i;}return ans;
}

• 三、双指针，思路及代码如上