接雨水

题目

思路

• 暴力解决
  • 求每一列能够保留多少水，因此我们会求左右最大列比当前列高的，然后选中两个中较小的一列，用它减去当前列就得到当前列所能够得到的积水。
  • 
• 动态规划
  • 就是把暴力优化了，把每次获取最大最小值的用数组存起来，这样就能一次循环即可。
• 单调栈
  • 通过计算当前左右列之间在某一层的面积，也就是计算局部的行面积，最终得到全部的积水面积

代码

    //1.列暴力
    public int trap(int[] height) {
        int ans = 0, size = height.length;
        for (int i = 0; i < size; i++) {
            int left = 0, right = 0;
            for (int j = i; j < size; j++) {
                left = Math.max(left, height[j]); 
            }
            for (int j = i; j >= 0; j--) {
                right = Math.max(right, height[j]);
            }
            ans += Math.min(left, right) - height[i];
        }
        return ans;
    }
    //2.动态规划
    public int trap(int[] height) {
         int ans = 0, size = height.length;
         if (size <= 1) return ans;
         int[] left = new int[size], right = new int[size];
         left[0] = height[0];
         right[size - 1] = height[size - 1];
         for (int i = 1; i < size; i++) {
             left[i] = Math.max(height[i], left[i - 1]);
         }
         for (int i = size - 2; i >= 0; i--) {
             right[i] = Math.max(height[i], right[i + 1]);
         }
         for (int i = 1; i < size - 1; i++) {
             ans += Math.min(left[i], right[i]) - height[i];
         }
         return ans;
     }    
    //3.单调栈
    public int trap(int[] height) {
        int size = height.length, ans = 0;
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < size; i++) {
            while (!stack.isEmpty() && height[stack.peek()] < height[i]) {
                int cur = stack.pop();
                if (stack.isEmpty()) break;
                int l = stack.peek(), r = i;
                int h = Math.min(height[r], height[l]) - height[cur];
                ans += (r - l - 1) * h;
            }
            stack.push(i);
        }
        return ans;
    }

接雨水