LeetCode题解——接雨水

LeetCode题解——接雨水

我的LeetCode代码集：https://github.com/cnamep001/LeetCode

原题链接：https://leetcode-cn.com/problems/trapping-rain-water/description/

题目描述：

思路一：利用栈

我们的栈stack中存储的是height数组的索引。如果指针cur指向的height数组中的值小于等于栈顶元素或者栈为空，我们就一直入栈，因此我们栈顶元素索引对应的height数组的值是整个栈中最小的。一旦指针cur指向的height数组中的值超过栈顶的元素索引对应的height数组的值，就代表栈顶元素有一个右边界。由于栈中的元素都是递减的，所以如果存在一个比栈顶元素大的栈中元素，则一定可以确定该横向区域内的盛水量。

时间复杂度是O(n)，空间复杂度是O(n)。

实现代码:

package com.m.trapping_rain_water.solution1;


import java.util.Stack;

public class Solution1 {

    public int trap(int[] height) {
        int n = height.length;
        int result = 0;
        if (n == 0 || n == 1) {
            return result;
        }
        int cur = 0;
        Stack<Integer> stack = new Stack<Integer>();
        while (cur < n) {
            while (!stack.isEmpty() && height[cur] > height[stack.peek()]) {
                int top = stack.pop();
                if (stack.isEmpty()) {
                    break;
                }
                int distance = cur - stack.peek() - 1;
                int tempHeight = Math.min(height[cur], height[stack.peek()]) - height[top];
                result += tempHeight * distance;
            }
            stack.push(cur);
            cur++;
        }
        return result;
    }

}

LeetCode解题报告：

思路二：用双指针法

（1）首先，找到能存水的左边界索引left和右边界索引right。

对于左边界索引left是从数组头到数组尾方向看，第一次出现下降趋势的那个索引的位置。

对于右边界索引right是从数组尾到数组头方向看，第一次出现下降趋势的那个索引的位置。

（2）记录左边界和右边界的高度，分别记作leftHeight和rightHeight。显然，雨水数是由较低的边界所决定的。

a.如果leftHeight小于等于rightHeight。

如果此时满足left < right，说明左右边界还没有重合，尝试着令left加1。如果left位置能够存储雨水，则更新结果的值。如果left位置不能存储雨水，说明left位置的高度大于等于leftHeight，这时我们应该进入下一轮循环，更新leftHeight的值。

b.如果leftHeight大于rightHeight

如果此时满足left < right，说明左右边界还没有重合，尝试着令right减1。如果right位置能够存储雨水，则更新结果的值。如果right位置不能存储雨水，说明right位置的高度大于等于rightHeight，这时我们应该进入下一轮循环，更新rightHeight的值。

该思路的时间复杂度是O(n)级别的，空间复杂度是O(1)级别的。

实现代码:

package com.m.trapping_rain_water.solution2;

public class Solution2 {

    public int trap(int[] height) {
        int n = height.length;
        int result = 0;
        if (n == 0 || n == 1) {
            return result;
        }
        int left = 0;
        while (left < n - 1 && height[left + 1] >= height[left]) {
            left++;
        }
        int right = n - 1;
        while (right >= 1 && height[right - 1] >= height[right]) {
            right--;
        }
        while (left < right) {
            int leftHeight = height[left];
            int rightHeight = height[right];
            if (leftHeight <= rightHeight) {
                while (left < right) {
                    left++;
                    if (height[left] < leftHeight) {
                        result += leftHeight - height[left];
                    } else {
                        break;
                    }
                }
            } else {
                while (left < right) {
                    right--;
                    if (height[right] < rightHeight) {
                        result += rightHeight - height[right];
                    } else {
                        break;
                    }
                }
            }
        }
        return result;
    }

}

LeetCode解题报告：

思路三：逐层累加法(会超时）

首先遍历数组得到最高的柱子的高度maxHeight，我们总共需要计算maxHeight层。

计算第i层时，我们需要将柱子的高度减去i，这里i从0开始计数。我们寻找每一层的左边界left和右边界right，在[left, right]之间高度小于等于0处，我们可以令能接的雨水数加1。

这个思路的时间复杂度很明显，是O(maxHeight * n)级别的，其中n为height数组的长度。而对于空间复杂度，我们使用了一个新的数组newHeight记录各柱子高度减去i时的值，因此是O(n)级别的。

实现代码:

package com.m.trapping_rain_water.solution3;


public class Solution3 {

    public int trap(int[] height) {
        int n = height.length;
        int result = 0;
        if (n == 0) {
            return result;
        }
        int maxHeight = height[0];
        for (int i = 1; i < n; i++) {
            if (height[i] > maxHeight) {
                maxHeight = height[i];
            }
        }
        int[] newHeight = new int[n];
        for (int i = 0; i < maxHeight; i++) {
            for (int j = 0; j < n; j++) {
                newHeight[j] = height[j] - i;
            }
            int left = 0;
            int right = n - 1;
            while (left < n && newHeight[left] <= 0) {
                left++;
            }
            while (right >= 0 && newHeight[right] <= 0) {
                right--;
            }
            for (int j = left; j <= right; j++) {
                if (newHeight[j] <= 0) {
                    result++;
                }
            }
        }
        return result;
    }

}