题解 | #接雨水问题#

双指针，但是更简单。

class Solution {
public:

	long long maxWater(vector<int>& arr) {
		// write code here
		int left = 1, right = arr.size() - 2;		//hole
		int h1 = arr[0], h2 = arr[arr.size() - 1];	//border
		int ans = 0;
		while (left <= right) {
			if (arr[left] >= h1) {	//h1 update
				h1 = arr[left];
				left++;
				continue;
			}
			if (arr[right] >= h2) {	//h2 update
				h2 = arr[right];
				right--;
				continue;
			}
			if (h1 < h2) {			//There exists water in left hole
				ans += h1 - arr[left];
				left++;
			}
			else{					//There exists water in right hole
				ans += h2 - arr[right];
				right--;
			}
		}
		return ans;
	}
};

再贴一个自测main函数：

int main() {
	ios::sync_with_stdio(0);	
	cin.tie(0);

//input
	string str;					
	stringstream ss;			
	getline(cin,str);
	ss << str;

//array initialise. separated by single space in a line. 
	int num;
	vector<int> arr;
	while (ss>>num) {
		arr.emplace_back(num);
	}

//water count
	Solution s;
	cout << s.maxWater(arr);
	return 0;
}

但这么简单的算法楞是想不到，把算法应用到具象问题的能力好重要哦。

----第二次编辑----

？？？'法'楞'是个什么和谐词，刚发出去的时候居然要标*** 我的知识又短浅了