/
number-of-people-that-can-be-seen-in-a-grid.py
96 lines (88 loc) · 2.97 KB
/
number-of-people-that-can-be-seen-in-a-grid.py
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
# Time: O(m * n)
# Space: O(m + n)
# mono stack, optimized from solution2
class Solution(object):
def seePeople(self, heights):
"""
:type heights: List[List[int]]
:rtype: List[List[int]]
"""
def count(h, stk):
cnt = 0
while stk and stk[-1] < h:
stk.pop()
cnt += 1
if stk:
cnt += 1
if not stk or stk[-1] != h:
stk.append(h)
return cnt
result = [[0]*len(heights[0]) for _ in xrange(len(heights))]
for i in xrange(len(heights)):
stk = []
for j in reversed(xrange(len(heights[0]))):
result[i][j] += count(heights[i][j], stk)
for j in xrange(len(heights[0])):
stk = []
for i in reversed(xrange(len(heights))):
result[i][j] += count(heights[i][j], stk)
return result
# Time: O(m * n)
# Space: O(m + n)
# mono stack
class Solution2(object):
def seePeople(self, heights):
"""
:type heights: List[List[int]]
:rtype: List[List[int]]
"""
def count(heights, i, stk):
cnt = 0
while stk and heights(stk[-1]) < heights(i):
stk.pop()
cnt += 1
if stk:
cnt += 1
if stk and heights(stk[-1]) == heights(i):
stk.pop()
stk.append(i)
return cnt
result = [[0]*len(heights[0]) for _ in xrange(len(heights))]
for i in xrange(len(heights)):
stk = []
for j in reversed(xrange(len(heights[0]))):
result[i][j] += count(lambda x: heights[i][x], j, stk)
for j in xrange(len(heights[0])):
stk = []
for i in reversed(xrange(len(heights))):
result[i][j] += count(lambda x: heights[x][j], i, stk)
return result
# Time: O(m * n)
# Space: O(m + n)
# mono stack
class Solution3(object):
def seePeople(self, heights):
"""
:type heights: List[List[int]]
:rtype: List[List[int]]
"""
def count(heights, i, stk, add):
while stk and heights(stk[-1]) < heights(i):
increase(stk.pop())
if stk:
increase(stk[-1])
if stk and heights(stk[-1]) == heights(i):
stk.pop()
stk.append(i)
result = [[0]*len(heights[0]) for _ in xrange(len(heights))]
for i in xrange(len(heights)):
stk = []
def increase(x): result[i][x] += 1
for j in xrange(len(heights[0])):
count(lambda x: heights[i][x], j, stk, add)
for j in xrange(len(heights[0])):
stk = []
def increase(x): result[x][j] += 1
for i in xrange(len(heights)):
count(lambda x: heights[x][j], i, stk, add)
return result