双指针遍历/滑动窗口 —— 42_接雨水

6. 42_接雨水

/*
上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）
*/

/*
暴力解， O(n²),O(1)
*/
class Solution {
    int trap(int[] height)
    {
        int ans = 0;
        int size = height.length;
        for (int i = 1; i < size - 1; i++) {
            int leftMax = 0, rightMax = 0;
            for (int j = i; j >= 0; j--) {
                leftMax = Math.max(leftMax, height[j]);
            }
            for (int j = i; j < size; j++) { 
                rightMax = Math.max(rightMax, height[j]);
            }
            ans += Math.min(leftMax, rightMax) - height[i];
        }
        return ans;
    }
}

/*
动态编程 O(n),O(n)
*/
class Solution {
    public int trap(int[] height)
    {
        if (height == null || height.length == 0)
            return 0;
        int ans = 0;
        int len = height.length;
        int[] leftMax = new int[len];
        int[] rightMax = new int[len];
        leftMax[0] = height[0];
        for (int i = 1; i < len; i++) {
            leftMax[i] = Math.max(height[i], leftMax[i - 1]);
        }
        rightMax[len - 1] = height[len - 1];
        for (int i = len - 2; i >= 0; i--) {
            rightMax[i] = Math.max(height[i], rightMax[i + 1]);
        }
        for (int i = 1; i < len - 1; i++) {
            ans += Math.min(leftMax[i], rightMax[i]) - height[i];
        }
        return ans;
    }
}

/*
栈的应用, O(n),O(n)（单调递减栈）
*/
class Solution {
    int trap(int[] height)
    {
        int ans = 0, cur = 0;
        Stack<Integer> st = new Stack<>();
        while (cur < height.length) {
            while (!st.isEmpty() && height[cur] > height[st.peek()]) {
                int top = st.peek();
                st.pop();
                if (st.isEmpty())
                    break;
                int distance = cur - st.peek() - 1;
                int boundedHeight = Math.min(height[cur], height[st.peek()]) - height[top];
                ans += distance * boundedHeight;
            }
            st.push(cur++);
        }
        return ans;
    }
}
/*
双指针，O(n),O(1)
*/
class Solution {
    int trap(int[] height)
    {
        int left = 0, right = height.length - 1;
        int ans = 0;
        int leftMax = 0, rightMax = 0;
        while (left < right) {
            if (height[left] < height[right]) {
                if(height[left] >= leftMax)
                    leftMax = height[left];
                else 
                    ans += (leftMax - height[left]);
                ++left;
            }
            else {
                if(height[right] >= rightMax)
                    rightMax = height[right];
                else 
                    ans += (rightMax - height[right]);
                --right;
            }
        }
        return ans;
    }
}