11. Container With Most Water
https://www.cnblogs.com/grandyang/p/4455109.html
用双指针向中间滑动，较小的高度就作为当前情况的高度，然后循环找容量的最大值。
不管两个指针中间有多少高度的柱子，只管两头，因为两头的才决定最大容量。
class Solution {
public:
int maxArea(vector<int>& height) {
if(height.empty())
return ;
int res = ;
int begin = ,end = height.size() - ;
while(begin < end){
int h = min(height[begin],height[end]);
res = max(res,(end - begin) * h);
h == height[begin] ? begin++ : end --;
}
return res;
}
};
42. Trapping Rain Water
https://www.cnblogs.com/grandyang/p/4402392.html
本题与11. Container With Most Water不同，11. Container With Most Water是求两个柱子能装的最多水量，这个题是求的所有柱子能装的水量。
依旧可以使用双指针，一个begin指向第一个柱子，一个end指向最后一个柱子。然后相当于维护一个递减的队列，但又不是完全递减，只是说后面遍历到的应该比这个开始的位置少。一旦出现比这个开始位置大，就要重新更新作为比较的对象。
注意，选择对比的是两个柱子中较短的那根柱子。
class Solution {
public:
int trap(vector<int>& height) {
int begin = ,end = height.size() - ;
int res = ;
while(begin < end){
int h = min(height[begin],height[end]);
if(h == height[begin]){
int tmp = height[begin];
begin++;
while(begin < end && height[begin] < tmp){
res += tmp - height[begin];
begin++;
}
}
else{
int tmp = height[end];
end--;
while(begin < end && height[end] < tmp){
res += tmp - height[end];
end--;
}
}
}
return res;
}
};
238. Product of Array Except Self
https://www.cnblogs.com/grandyang/p/4650187.html
整体分成左右两个数组进行相乘，这种方式不用两个数组进行存储。
从左向右可以用res[i]就代替前面的乘积，但从右向左就不行了，这个是后res[i]已经是所有的在左侧前方的乘积和，我们还必须计算右侧的乘积和，这个时候用一个变量right来累乘就好了。
其实从左向右也可以用一个变量来累乘。
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
vector<int> res(nums.size(),);
for(int i = ;i < nums.size();i++){
res[i] = res[i-] * nums[i-];
}
int right = ;
for(int i = nums.size() - ;i >= ;i--){
res[i] *= right;
right *= nums[i];
}
return res;
}
};
407. Trapping Rain Water II
https://www.cnblogs.com/grandyang/p/5928987.html
class Solution {
public:
int trapRainWater(vector<vector<int>>& heightMap) {
if(heightMap.empty())
return ;
int m = heightMap.size(),n = heightMap[].size();
int res = ,max_height = INT_MIN;
vector<vector<bool>> visited(m,vector<bool>(n,false));
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q;
for(int i = ;i < m;i++){
for(int j = ;j < n;j++){
if(i == || i == m - || j == || j == n - ){
int index = i * n + j;
q.push(make_pair(heightMap[i][j],index));
visited[i][j] = true;
}
}
}
while(!q.empty()){
int height = q.top().first;
int x = q.top().second / n;
int y = q.top().second % n;
q.pop();
max_height = max(max_height,height);
for(auto dir : dirs){
int new_x = x + dir[];
int new_y = y + dir[];
if(new_x < || new_x >= m || new_y < || new_y >= n || visited[new_x][new_y] == true)
continue;
visited[new_x][new_y] = true;
if(heightMap[new_x][new_y] < max_height)
res += max_height - heightMap[new_x][new_y];
int new_index = new_x * n + new_y;
q.push(make_pair(heightMap[new_x][new_y],new_index));
}
}
return res;
}
private:
vector<vector<int>> dirs{{-,},{,-},{,},{,}};
};