#pragma warning(disable:4996)

#include <cstdio>
#include <tchar.h>
#include <Windows.h>

/*
	submit time : 3
		1.Time Limit Exceeded
			Last executed input:	[]		
		2.Cant‘s remember
	request :
		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.
*/

int helpMin(int i, int j) {
	return i < j ? i : j;
}

void helpTrap(int& water, int* data, int length, int l, int r) {
	if (r - l <= 1) return;		// do not calculate one or two numbers

	// find two biggest numbers
	int big1value = 0, big2value = 0;
	int big1index = 0, big2index = 0;
	int vernier = l;
	while (vernier <= r) {
		if (data[vernier] >= big1value) {
			if (data[vernier] >= big2value) {
				big1index = big2index;
				big1value = big2value;
				big2index = vernier;
				big2value = data[vernier];
			}
			else {
				big1index = vernier;
				big1value = data[vernier];
			}
		}
		++vernier;
	}

	// calculate current trap
	int lr = helpMin(big1index, big2index), rl = big1index + big2index - lr;
	int currWater = 0;
	vernier = lr;
	while (++vernier < rl)
		water += (big1value - data[vernier]);

	// calculate other two sides
	helpTrap(water, data, length, l, lr);
	helpTrap(water, data, length, rl, r);
}

int trap(int A[], int n) {
	if (A == NULL || n <= 2) return 0;

	int water = 0;
	helpTrap(water, A, n, 0, n - 1);

	return water;
}

//============Test==================
void Test(const char* testName, int* data, int length) {
	printf("%s begins:\n", testName);

	int result = trap(data, length);
	printf("%d\n", result);
}

void Test1() {
	int data[] = { 0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1 };
	Test("Test1", data, sizeof(data) / sizeof(int));
}

void Test2() {
	int data[] = { 0, 1, 2, 3, 3, 3, 3, 3, 2, 1 };
	Test("Test2", data, sizeof(data) / sizeof(int));
}

void Test3() {
	int data[] = { 0, 1, 2, 3, 4, 5, 1, 2 };
	Test("Test3", data, sizeof(data) / sizeof(int));
}

void Test4() {
	int data[] = { 100, 0,0,1,0,0, 1000 };
	Test("Test4", data, sizeof(data) / sizeof(int));
}

void Test5() {
	int data[] = { 5,2,1,2,1,5 };
	Test("Test5", data, sizeof(data) / sizeof(int));
}

int _tmain(int argc, _TCHAR* argv[]) {
	Test1();
	Test2();
	Test3();
	Test4();
	Test5();

	system("pause");
	return 0;
}

LeetCode_41trap [Trapping Rain Water],布布扣,bubuko.com

LeetCode_41trap [Trapping Rain Water]