1. 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.
Solution: Find left bound and right bound for each element. O(n).
1 class Solution { 2 public: 3 int trap(int A[], int n) { 4 int max_val = 0; 5 int max_ind = 0; 6 for(int i = 0; i < n; i++) { 7 if(A[i] > max_val) { 8 max_val = A[i]; 9 max_ind = i; 10 } 11 } 12 13 int trap = 0; 14 int start = 0; 15 for(int i = start+1; i < max_ind; i++) { 16 if(A[i] < A[start]) { 17 trap += A[start]-A[i]; 18 } 19 else { 20 start = i; 21 } 22 } 23 24 start = n-1; //update start 25 for(int i = start-1; i > max_ind; i--) { 26 if(A[i] < A[start]) { 27 trap += A[start]-A[i]; 28 } 29 else{ 30 start = i; 31 } 32 } 33 return trap; 34 } 35 };
2. 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.
Solution: From both sides to the center.
1 class Solution { 2 public: 3 int maxArea(vector<int> &height) { 4 int res = 0; 5 int l = 0, r = height.size()-1; 6 while (l < r) { 7 if (height[l] <= height[r]) { 8 res = max(res, (r-l) * height[l]); 9 l++; 10 } 11 else { 12 res = max(res, (r-l) * height[r]); 13 r--; 14 } 15 } 16 return res; 17 } 18 };
Leetcode个人总结9 数组题(2),布布扣,bubuko.com
原文：http://www.cnblogs.com/zhengjiankang/p/3627191.html