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

You may also like...

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注