算法&OJ--其他--接水装水问题

发表于 | 分类于 | 阅读次数:
  • 总结LintCode上两类看起来类似的问题
    • 装水问题
    • 接水问题

LintCode-383.装最多水的容器

给定 n 个非负整数 a1, a2, …, an, 每个数代表了坐标中的一个点 (i, ai)。画 n 条垂直线，使得 i 垂直线的两个端点分别为(i, ai)和(i, 0)。找到两条线，使得其与 x 轴共同构成一个容器，以容纳最多水。注意：容器不可倾斜。

  • 暴力遍历
    • 每条线和之前所有线计算
    • 记录最大值
    • 时间复杂度：O(n^2)
  • 示例解法
    • 两个指针分别从数组两端开始向中间遍历(分别找到高度不为零的竖边)
    • 每次计算面积，并记录最大值
    • 将较低高度的指针移动一位
    • 遍历整个数组
    • 时间复杂度：O(n)
  • 就示例解法me的思考

从两端逼近，容器X轴边长单调减小，要使面积增大的话，必须增大宽，所以保留长的竖边

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 示例AC代码
public class Solution {
    // for any i, the maxium area will be the farthest j that has a[j] > a[i];
    public int maxArea(int[] height) {
        if(height == null || height.length < 2) {
            return 0;
        }
        int max = 0;
        int left = 0;
        int right = height.length -1;
        while(left < right) {
            max = Math.max( max, 
                    (right - left) * Math.min(height[left],height[right]));
            if(height[left] < height[right]){
                left++;
            } else {
                right--;
            }
        }
        return max;
        
    }
}

LintCode-363.接雨水 系列一

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

image

  • 注意：此时竖边是有宽度的。

此题本质：某一bar的接水量=min(左边bar最大高度，右边bar最大高度)-bar高

  • 最直接的做法
    • 双数组，一个储存左边bar最大高度，一个储存右边bar最大高度
  • 有点绕的最优解
    • 两个记录最大高度的数组，自最大值出现后就不会被调用了(因为取得是min值)
    • 采用对撞型指针，每次让高度较小的指针移动即可
    • 该指针处接水量即为该方向最大值减去该处bar高
    • 循环直至两指针相遇于最高处
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public int trapRainWater(int[] heights) {
    // 双指针问题
    if(heights==null || heights.length<2) {
        return 0;
    }
    int water = 0;
    int left = 0;
    int right = heights.length - 1;
    int lMax = 0;
    int rMax = 0;
    while(left < right) {
        lMax = max(lMax, heights[left]);
        rMax = max(rMax, heights[right]);
        if(lMax < rMax) {
            water += lMax - heights[left];
            left++;
        } else {
            water += rMax - heights[right];
            right--;
        }
    }
    return water;
}
    
public int max(int a, int b) {
    return a>b?a:b;
}

LintCode-364.接雨水 系列二

Given n x m non-negative integers representing an elevation map 2d where the area of each cell is 1 x 1, compute how much water it is able to trap after raining.

  • emmm 此题感觉难度过大。暂不研究