题目描述

力扣题目链接

解题思路

具体解析参照：cart的题解

双指针

/**
        * 双指针法
        * 时间复杂度为O(n^2)。 空间复杂度为O(1)。
        *
        * @param height
        * @return
        */
public int trap(int[] height) {
    int sum = 0;
    for (int i = 0; i < height.length; i++) {
        // 第一个和最后一个不接雨水
        if (i == 0 && i == height.length - 1) continue;
        int rHeight = height[i]; // 记录左边柱子的最高高度
        int lHeight = height[i]; // 记录右边柱子的最高高度
        for (int r = i + 1; r < height.length; r++) {
            if (height[r] > rHeight) rHeight = height[r];
        }
        for (int l = i - 1; l >= 0; l--) {
            if (height[l] > lHeight) lHeight = height[l];
        }
        int temp = Math.min(lHeight, rHeight) - height[i];  // 左右两边最小的柱子减去本身主子高度，相当于接多少雨水
        if (temp > 0) sum += temp;  // 大于0才是将雨水加上去
    }
    return sum;
}

dp

/**
        * 动态规划
        *
        * @param height
        * @return
        */
public int trap(int[] height) {
    // 为了得到两边的最高高度，使用了双指针来遍历，每到一个柱子都向两边遍历一遍，这其实是有重复计算的。
    // 我们把每一个位置的左边最高高度记录在一个数组上（maxLeft），右边最高高度记录在一个数组上（maxRight）。
    // 这样就避免了重复计算，这就用到了动态规划。
    int size = height.length;
    int[] maxLeft = new int[size];
    int[] maxRight = new int[size];
    int sum = 0;
    // 即从左向右遍历：maxLeft[i] = max(height[i], maxLeft[i - 1]);
    // 从右向左遍历：maxRight[i] = max(height[i], maxRight[i + 1]);
    maxLeft[0] = height[0]; // 第一个元素的左边最大值就是本身
    for (int i = 1; i < size; i++) {
        maxLeft[i] = Math.max(maxLeft[i - 1], height[i]);
    }
    maxRight[size - 1] = height[size - 1];
    for (int i = size - 2; i > 0; i--) {
        maxRight[i] = Math.max(maxRight[i + 1], height[i]);
    }
    // 求和
    for (int i = 0; i < size; i++) {
        int temp = Math.min(maxLeft[i], maxRight[i]) - height[i];
        if (temp > 0) {
            sum += temp;
        }
    }
    return sum;
}

⭐单调栈

/**
        * 单调栈
        *
        * @param height
        * @return
        */
public int trap(int[] height) {
    // 两个柱子无法接雨水
    if (height.length <= 2) {
        return 0;
    }
    Stack<Integer> stack = new Stack<>();   // 栈顶到栈底从小到大
    stack.push(0);
    int sum = 0;
    for (int i = 1; i < height.length; i++) {
        // 如果当前遍历的元素（柱子）高度小于栈顶元素的高度，就把这个元素加入栈中，因为栈里本来就要保持从小到大的顺序（从栈头到栈底）。
        if (height[stack.peek()] > height[i]) {
            stack.push(i);
            // 如果当前遍历的元素（柱子）高度等于栈顶元素的高度，要跟更新栈顶元素，因为遇到相相同高度的柱子，需要使用最右边的柱子来计算宽度。
        } else if (height[stack.peek()] == height[i]) {
            stack.pop();
            stack.push(i);
        } else if (height[stack.peek()] < height[i]) {
            //                    取栈顶元素，将栈顶元素弹出，这个就是凹槽的底部，也就是中间位置，下标记为mid，对应的高度为height[mid]（就是图中的高度1）。
            //                    此时的栈顶元素st.top()，就是凹槽的左边位置，下标为st.top()，对应的高度为height[st.top()]（就是图中的高度2）。
            //                    当前遍历的元素i，就是凹槽右边的位置，下标为i，对应的高度为height[i]（就是图中的高度3）。
            //                    此时大家应该可以发现其实就是栈顶和栈顶的下一个元素以及要入栈的三个元素来接水！
            //                    那么雨水高度是 min(凹槽左边高度, 凹槽右边高度) - 凹槽底部高度，代码为：int h = min(height[st.top()], height[i]) - height[mid];
            //                    雨水的宽度是 凹槽右边的下标 - 凹槽左边的下标 - 1（因为只求中间宽度），代码为：int w = i - st.top() - 1 ;
            //                    当前凹槽雨水的体积就是：h * w。
            while (!stack.isEmpty() && height[stack.peek()] < height[i]) {  // 循环计算，多次凹槽的雨水
                Integer mid = stack.peek();
                stack.pop();
                if (!stack.isEmpty()) { // 注意判断左边是否由元素
                    Integer left = stack.peek();
                    int high = Math.min(height[left], height[i]) - height[mid]; // 求出高度
                    int width = i - left - 1;   // 求出宽度，只求中间的宽度，所以需要再减一
                    int size = high * width;    // 求出面积，为什么使用面积来记录雨水多大呢？ 因为，因为你在相同时入了新的地址，所以中间可能有多个空隙，所以需要使用面积计算
                    if (size > 0) sum += size;
                }
            }
            stack.push(i);  // 最后还要将将要入栈的柱子入栈，接下一次水
        }
    }
    return sum;
}