代码随想录算法训练营第五十九天|503.下一个更大元素II、42. 接雨水

卡尔说：接雨水这道题目是面试中特别高频的一道题，也是单调栈应用的题目，大家好好做做。建议是掌握?双指针?和单调栈，因为在面试中写出单调栈可能有点难度，但双指针思路更直接一些。在时间紧张的情况有，能写出双指针法也是不错的，然后可以和面试官在慢慢讨论如何优化。

方法一：暴力解法

思路：以求解列4的雨水量进行思考

列4的雨水高度为列3和列7的高度最小值减列4高度，即： min(lHeight, rHeight) - height。

列4的雨水高度求出来了，宽度为1，相乘就是列4的雨水体积了。

要注意第一个柱子和最后一个柱子不接雨水。

class Solution {
    public int trap(int[] height) {
        int sum = 0;
        for (int i = 1; i < height.length - 1; i++) {
            //注意第一个和最后一个柱子不接水
            int rHeight = 0; // 每次循环都需要更新，所以应当写在循环里面
            int lHeight = 0; // 每次循环都需要更新，所以应当写在循环里面
            for (int l = 0; l < i; l++) {
                //寻找该列左边的最大高度
            //也可以修改遍历顺序为
            //for (int l = i - 1; l >= 0; l--) { 
                lHeight = Math.max(lHeight, height[l]);
            }
            for (int r = i + 1; r < height.length; r++) {
                //寻找该列右边的最大高度
                rHeight = Math.max(rHeight, height[r]);
            }
            int h = Math.min(lHeight, rHeight) - height[i];
            if (h > 0){
                sum += h;
            }
        }
        return sum;
    }
}

方法二：双指针法

为了得到两边的最高高度，使用了双指针来遍历，每到一个柱子都向两边遍历一遍，这其实是有重复计算的。我们把每一个位置的左边最高高度记录在一个数组上（maxLeft），右边最高高度记录在一个数组上（maxRight），这样就避免了重复计算。

当前位置，左边的最高高度是前一个位置的左边最高高度和本高度的最大值。

即从左向右遍历：maxLeft[i] = max(height[i], maxLeft[i - 1]);

从右向左遍历：maxRight[i] = max(height[i], maxRight[i + 1]);

//注意遍历顺序，因为需要先知道maxRight[i + 1]，所以需要从右向左遍历

class Solution {
    public int trap(int[] height) {
        int len = height.length;
        if (len <= 2){
            return 0;
        }
        int[] maxLeft = new int[len];
        int[] maxRight = new int[len];
        int sum = 0;
        // 记录每个柱子左边柱子最大高度
        maxLeft[0] = height[0];
        for (int i = 1; i < len; i++) {//第一个不装雨水
            maxLeft[i] = Math.max(height[i], maxLeft[i - 1]);
        }
        maxRight[len - 1] = height[len - 1];
        for (int i = len - 2; i >= 0; i--) {//最后一个不装雨水，注意遍历顺序
        // maxRight[0] = height[0];
        // for (int i = 0; i < len - 1; i++) {
        //遍历顺序不可修改为此，因为遍历的时候需要先知道maxRight[i + 1]，所以必须倒序遍历
            maxRight[i] = Math.max(height[i], maxRight[i + 1]);
        }
        for (int i = 0; i < len; i++) {
            int h = Math.min(maxLeft[i], maxRight[i]) - height[i];
            if (h > 0){
                sum += h;
            }
        }
        return sum;
    }
}

方法三：单调栈

错误：?while (!st.isEmpty() && height[i] > height[st.peek()])，一开始写成了?while (!st.isEmpty() && height[i] > st.peek())，最后debug之后发现问题了，一定要注意单调栈里面存的是下标，但是比较的应当是元素

class Solution {
    public int trap(int[] height) {
        if(height.length <= 2){
            return 0;
        }
        Stack<Integer> st = new Stack<Integer>();
        st.push(0);//单调栈里面存放遍历过的元素的下标
        int sum = 0;
        for (int i = 1; i < height.length; i++) {
            while (!st.isEmpty() && height[i] > height[st.peek()]){
                //st.peek()是下标，height[st.peek()才是比较的元素！
                int mid = st.peek();//因为后面弹出后还要用到，所以需要提前存一下
                st.pop();
                if (!st.empty()) {
                    //有可能上面判断的时候还不为空，后面弹出元素之后栈为空，所以此处还需要再次判断一下
                    int h = Math.min(height[st.peek()], height[i]) - height[mid];
                    int w = i - st.peek() - 1;
                    sum += h * w;
                }
            }
            st.push(i);
        }
        return sum;
    }
}