题解 | #接雨水问题#

接雨水问题

http://www.nowcoder.com/practice/31c1aed01b394f0b8b7734de0324e00f

双指针,但是更简单。

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;
}

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

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

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

全部评论

相关推荐

04-29 22:35
门头沟学院 Java
牛友说改了名字能收到offer:旧图新发查看图片
点赞 评论 收藏
分享
05-03 12:45
西南大学 Java
sdgfdv:你这项目写的内容太多了,说实话都是在给自己挖坑,就算简历过了,后面面试也难受
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务