-
Notifications
You must be signed in to change notification settings - Fork 1
/
trap.go
132 lines (125 loc) · 2.85 KB
/
trap.go
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
package trap
import (
"github.com/catorpilor/leetcode/utils"
)
func Trap(nums []int) int {
n := len(nums)
if n <= 2 {
return 0
}
// same as largest ractangle in histogram
// use stack to store indexes.
s := utils.NewStack()
var i, ret int
for i < n {
if s.IsEmpty() || nums[s.Top().(int)] >= nums[i] {
s.Push(i)
i++
} else {
v := s.Pop().(int) // bottom
// nums[i] represents the right boundary
if !s.IsEmpty() { // left boundary found
top := s.Top().(int)
// nums[top] represents the left bounday
// we have to find the minimal one
ret += (utils.Min(nums[top], nums[i]) - nums[v]) * (i - top - 1)
}
}
}
return ret
}
func useTwoPointers(nums []int) int {
// O(n) time and O(1) space
n := len(nums)
if n <= 2 {
return 0
}
left, right, maxLeft, maxRight := 0, n-1, nums[0], nums[n-1]
var res int
// Search from left to right and maintain a max height of left and right separately,
// which is like a one-side wall of partial container.
// Fix the higher one and flow water from the lower part.
// For example, if current height of left is lower, we fill water in the left bin.
// Until left meets right, we filled the whole container.
for left < right {
/*
if nums[left] <= nums[right] {
if nums[left] >= maxLeft {
maxLeft = nums[left]
} else {
res += maxLeft - nums[left]
}
left++
} else {
if nums[right] >= maxRight {
maxRight = nums[right]
} else {
res += maxRight - nums[right]
}
right--
}
*/
if maxLeft < maxRight {
res += maxLeft - nums[left]
left++
maxLeft = utils.Max(maxLeft, nums[left])
} else {
res += maxRight - nums[right]
right--
maxRight = utils.Max(maxRight, nums[right])
}
}
return res
}
// bruteForce time complexity O(N^2), space complexity O(1)
func bruteForce(nums []int) int {
n := len(nums)
if n <= 2 {
return 0
}
var res, maxL, maxR int
for i := range nums {
// maxL the max height of nums[0:i]
// maxR the max height of nums[i+1:]
maxL, maxR = 0, 0
for j := 0; j < i; j++ {
if nums[j] > maxL {
maxL = nums[j]
}
}
for j := i + 1; j < n; j++ {
if nums[j] > maxR {
maxR = nums[j]
}
}
units := utils.Min(maxL, maxR) - nums[i]
if units > 0 {
res += units
}
}
return res
}
// dp same idea as bruteForce, but use two slice to store the max height
// from both directions, time complexity is 0(N), space complexity is O(N)
func dp(nums []int) int {
n := len(nums)
if n <= 2 {
return 0
}
// maxL and maxR are the prefix/post Max array
maxL := make([]int, n)
maxL[0] = nums[0]
for i := 1; i < n; i++ {
maxL[i] = utils.Max(nums[i], maxL[i-1])
}
maxR := make([]int, n)
maxR[n-1] = nums[n-1]
for i := n - 2; i >= 0; i-- {
maxR[i] = utils.Max(nums[i], maxR[i+1])
}
var res int
for i := 1; i < n-1; i++ {
res += utils.Min(maxL[i], maxR[i]) - nums[i]
}
return res
}