11.Container With Most Water

Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Note: You may not slant the container.

S: two pinter, recursion O(n)

对于由ai,aj(i<j)组成的container Area(ai,aj)其容积是由较短的板决定的。若ai<aj,都有MaxArea(ai,aj)=max(Area(ai,aj), MaxArea(ai+1,aj)).

int maxArea(vector<int>& height) {
       return findMax(height, 0, height.size()-1); 
    }

    int findMax(vector<int>& height, int left, int right){
        if(left == right) return 0;
        int currentArea = (right - left) * min(height[left], height[right]);
        if(height[left] <= height[right]) {
            return max(findMax(height, left+1, right), currentArea); 
        }
        else return max(findMax(height, left, right-1), currentArea);
    }

iteration version:

int maxArea(vector<int>& height) {
       int max = 0;
       int l = 0, r = height.size() - 1;
       while(l < r){
           int currentArea = (r - l) * min(height[l], height[r]);
           if(currentArea > max) max = currentArea;
           if(height[l] <= height[r]) l++;
           else r--;
       }
       return max;
    }

42. Trapping Rain Water

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.
For example,
Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.

The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!

S: two pointer O(n)time O(1)space.
建模：两边到中间，水的加和减

    int trapRainWater(vector<int> &heights) {
        int water = 0, bar = 0;
        int l = 0, r = heights.size()-1;
        while(l < r){
            int newBar = min(heights[l], heights[r]);
            if(newBar <= bar) {
                water -= newBar;
            } else{
                water += (r - l - 1) * (newBar - bar)- bar;
                bar = newBar;
            }
            if(heights[l] > heights[r]) {
                r--;
            } else {
                l++;
            }
        }
        return water;
    }

407. Trapping Rain Water II

Given anm x nmatrix of positive integers representing the height of each unit cell in a 2D elevation map, compute the volume of water it is able to trap after raining.

Note:
Both m and n are less than 110. The height of each unit cell is greater than 0 and is less than 20,000.

Example:

Given the following 3x6 height map:
[
  [1,4,3,1,3,2],
  [3,2,1,3,2,4],
  [2,3,3,2,3,1]
]

Return 4.

S：heap O（mnlogmn)

1. 找外围,存入minheap
2. 从瓶颈点向内找最小，并更新heap

更新heap: 每次pop当前瓶颈节点并存入內围节点坐标，若內围节点height高于当前瓶颈高度，存入內围节点高度，否则在新节点仍然存入当前瓶颈高度

struct Node {
  int x;
  int y;
  int height;
  Node(int i, int j, int h): x(i), y(j), height(h) {}
};

struct cmp {
    bool operator() (const Node* a, const Node* b) const{
        return a->height > b->height;
    }
};
class Solution {
public:
    int trapRainWater(vector<vector<int>>& heightMap) {
        int m = heightMap.size();
        if (m < 3) {
            return 0;
        }
        int n = heightMap[0].size();
        if (n < 3) {
            return 0;
        }
        vector<vector<bool>> visited(m, vector<bool>(n, false));
        priority_queue<Node*, vector<Node*>, cmp> minHeap;
        int result = 0;
        for (int i = 0; i < m; ++i) {
            Node* node1 = new Node(i, 0, heightMap[i][0]);
            minHeap.push(node1);
            Node* node2 = new Node(i, n - 1, heightMap[i][n - 1]);
            minHeap.push(node2);
            visited[i][0] = true;
            visited[i][n - 1] = true;
        }
        for (int i = 1; i < n - 1; ++i) {
            Node* node1 = new Node(0, i, heightMap[0][i]);
            minHeap.push(node1);
            Node* node2 = new Node(m - 1, i, heightMap[m - 1][i]);
            minHeap.push(node2);
            visited[0][i] = true;
            visited[m - 1][i] = true;
        }
        vector<int> dx{0, 1, 0, -1};
        vector<int> dy{1, 0, -1, 0};
        while (!minHeap.empty()) {
            Node* cur = minHeap.top();
            minHeap.pop();
            for(int k = 0; k < 4; ++k) {
                int x = cur->x + dx[k];
                int y = cur->y + dy[k];
                if (x > 0 && x < m && y >0 && y < n &&
                    !visited[x][y]) {
                    int h = heightMap[x][y];
                    result += max(0, cur->height - h);
                    h = max(h, cur->height); //keep the original height if current height is lower
                    Node* node = new Node(x, y, h);
                    minHeap.push(node);
                    visited[x][y] = true;
                }
            }
        }
        return result;
    }
};