-
Notifications
You must be signed in to change notification settings - Fork 2
/
q0042.c
133 lines (125 loc) · 3.85 KB
/
q0042.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
//
// q0042.c
// LeetCode
//
// Created by NowOrNever on 22/10/2019.
// Copyright © 2019 DoubleL. All rights reserved.
//
#include "q0042.h"
#include "../common.h"
//42. Trapping Rain Water
//Hard
//
//2918
//
//51
//
//Favorite
//
//Share
//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.
//
//
//The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!
//
//Example:
//
//Input: [0,1,0,2,1,0,1,3,2,1,2,1]
//Output: 6
//Accepted
//252,295
//Submissions
//605,652
/**
int trap(int* height, int heightSize) {
if (heightSize <= 1) {
return 0;
}
int result = 0;
int *newHeights = calloc(heightSize, sizeof(int));
memcpy(newHeights, height, heightSize * sizeof(int));
qsort(newHeights, heightSize, sizeof(int), compareIntFunction);
int count = 1;
for (int i = 1; i < heightSize; i++) {
if (newHeights[i] > newHeights[i - 1]) {
// printf("\nnewheight[%d] = %d",count, newHeights[i]);
newHeights[count++] = newHeights[i];
}
}
int lastLeft = heightSize - 1;
int lastRight = 0;
int firstTimeFlag = true;
for (int i = count - 1; i >= 0; i--) {
// printf("\ncurretn number %d result %d", newHeights[i], result);
int left = 0;
int right = heightSize - 1;
while (left < heightSize && height[left++] < newHeights[i]) {
}
while (right >= 0 && height[right--] < newHeights[i]) {
}
left--;
right++;
if (firstTimeFlag) {
firstTimeFlag = false;
for (int j = left; j < right; j++) {
if (newHeights[i] > height[j]) {
result = result + newHeights[i] - height[j];
}
}
}else{
for (int j = left; j < lastLeft; j++) {
if (newHeights[i] > height[j]) {
result = result + newHeights[i] - height[j];
}
}
for (int j = right; j > lastRight; j--) {
if (newHeights[i] > height[j]) {
result = result + newHeights[i] - height[j];
}
}
}
lastLeft = left;
lastRight = right;
}
return result;
}
*/
int MinInt(int a, int b){
return a < b ? a : b;
}
int trap(int* height, int heightSize) {
if (heightSize <= 1) {
return 0;
}
int result = 0;
int stackIndex = 0;
int stackSize = heightSize;
int stackIndexArray[stackSize];
int stackHeightArray[stackSize];
memset(stackIndexArray , 0, stackSize * sizeof(int));
memset(stackHeightArray, 0, stackSize * sizeof(int));
stackIndexArray[stackIndex] = 0;
stackHeightArray[stackIndex] = height[0];
for (int i = 1; i < heightSize; i++) {
while (stackIndex >= 0 && height[i] >= stackHeightArray[stackIndex]) {
if (stackIndex > 0) {
// printf("\nresult(%d) i(%d) stackIndex(%d) ; %d * (%d - %d)",result, i, stackIndex, (i - stackIndexArray[stackIndex - 1] - 1),MIN(stackHeightArray[stackIndex - 1], height[i]), stackHeightArray[stackIndex]);
result += (i - stackIndexArray[stackIndex - 1] - 1) * (MinInt(stackHeightArray[stackIndex - 1], height[i]) - stackHeightArray[stackIndex]);
}
stackIndex--;
}
stackIndex++;
stackHeightArray[stackIndex] = height[i];
stackIndexArray[stackIndex] = i;
}
return result;
}
int question42(){
int nums[] =
{4,2,3};
// {2,0,2};
// {0,1,0,2,1,0,1,3,2,1,2,1};
int result = trap(nums, sizeof(nums) / sizeof(nums[0]));
printf("\ntrap %d",result);
return 0;
}