LeetCode-困难-42-接雨水-双指针/快速排序(C)

LeetCode题解目录

我这次的题图好传神！

题目

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

示例 1：

输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
示例 2：

输入：height = [4,2,0,3,2,5]
输出：9
 

提示：

n == height.length
0 <= n <= 3 * 104
0 <= height[i] <= 105

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/trapping-rain-water
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

• 先讲一下思考过程：
  • 根据这题的样子，首先能想到每格的雨水是如何计算的。
  • 但这里的雨水，如果取得少了，又会因为更高的地方，涨上来。
  • 于是先想到了找极值点，这样就能把每个最高点都取出来。
  • 但最高点不一定就不会被雨水淹没，所以又打算对这些最高点再取一次极值点，
  • 如此循环，最后会剩两个最高点。
  • 这两个最高点中间的雨水，一定会涨到min(height1, height2)的高度上。
  • 那么左边次高的点，也是如此计算，右边亦然。
  • 如此循环，就能计算出来。
  • 然后简化了一下过程，发现这个就是从高到低排序分配雨水，于是有了下面更简单的思路。
• 下面是正文：
  • 先定义一个softResult[] = {0, 1, 2, 3, ......, n-1}，用来表示height的下标。
  • 然后使用快速排序，将下标，按其height[]里的值，从高到低排序。
    • 如果直接排序height[]，那么雨水就接不到了。
  • 排序完，定义两个指针left与right：
    • 其中，left表示目前雨水已填充的左边界，right表示右边界。
    • 刚开始时，left与right都在最高点，即softResult[0]。
    • 这个是用来防止重复加水的，水是生命之源，要节约用水。
  • 再来一个循环，从pos = 1开始，遍历softResult：
    • 如果softResult[pos]在left左边，为其中间的空位填充雨水，在right右边，亦然。
    • 每次填充完雨水，left与right都会相应移动，到填充过雨水的边界。
    • 当遍历完softResult，雨水也分配完了。
      • 实际上，当left与right到达数组边界的时候，已经可以提前结束了，但下面的代码没有这样做。
      • 究其原因，是因为当时我没想到。
  • 雨水的填充：
    • 雨水会填充与两个高点的中间，这两个高点中，较低的点的高度，就是雨水将填充到的高度。
    • 将这个高度，减去地面的高度，就能获得雨水的体积了。
• 优化方向：
  • 提高排序效率：
    • 感觉我写的快速排序效率不高，我还是第一次实际用它，没怎么理解，就是直接改改上来的。
    • 没有根据这个问题优化一下。
    • 以及可能因为是递归，所以内存用了不少。
  • 提高填充雨水效率：
    • 就是判断下left与right是否到数组边界，到了边界提前结束分配，感觉会减少些计算量。
    • 但同时又增加了判断边界的计算量，不好说会不会快。
    • 因为排名连80都上不去，就不改了。

代码

int trap(int* height, int heightSize){
    if(heightSize == 0) return 0;
    int pos, sum = 0, left, right, pos2;
    int* softResult = malloc(sizeof(int) * heightSize);
    for(pos = 0;    pos < heightSize;   pos++)
        softResult[pos] = pos;
    quickSoft(height, 0, heightSize-1, softResult);
    left = right = softResult[0];
    for(pos = 1;    pos < heightSize;   pos++){
        if(softResult[pos] < left){
            for(pos2 = softResult[pos] + 1; pos2 < left; pos2++){
                if(height[softResult[pos]] < height[pos2]) continue;
                sum += height[softResult[pos]] - height[pos2];
            }
            left = softResult[pos];
        }
        else if(softResult[pos] > right){
            for(pos2 = right + 1; pos2 < softResult[pos]; pos2++){
                if(height[softResult[pos]] < height[pos2]) continue;
                sum += height[softResult[pos]] - height[pos2];
            }
            right = softResult[pos];
        }
    }
    return sum;

}

void quickSoft(int *height, int left, int right, int* softResult){
    if (left > right) return;         
    int cLeft = left;
    int cRight = right;
    int standardPos = softResult[cLeft];
    while(cLeft<cRight){
        while(cLeft<cRight && height[standardPos] >= height[softResult[cRight]]) 
            cRight -= 1;
        if(cLeft<cRight)
            softResult[cLeft] = softResult[cRight];
        while(cLeft<cRight && height[standardPos] <= height[softResult[cLeft]])
            cLeft += 1;
        if(cLeft<cRight)
            softResult[cRight] = softResult[cLeft];
    }
    softResult[cLeft] = standardPos;
    quickSoft(height, left, cLeft-1, softResult);
    quickSoft(height, cLeft+1, right, softResult);
}