难度: Medium
Submission
运行时间: 214 ms
内存: 27.6 MB
class Solution:
def seePeople(self, heights: List[List[int]]) -> List[List[int]]:
m, n = len(heights), len(heights[0])
colStacks = [[] for _ in range(n)]
rowStack = []
answer = [[0]*n for _ in range(m)]
for r in range(m-1, -1, -1):
row, ansRow = heights[r], answer[r]
rowStack.clear()
for c in range(n-1, -1, -1):
v = row[c]
colStack = colStacks[c]
for stack in [rowStack, colStack]:
last = -inf
while stack and stack[-1] <= v:
last = stack.pop()
ansRow[c] += 1
if last < v and stack:
ansRow[c] += 1
stack.append(v)
return answer
Explain
这个题解的主要思路是利用栈（stack）来解决问题。算法从网格的右下角开始，逐行逆序遍历每个格子。对于每个格子，使用两个栈，一个是处理当前行的栈（rowStack），另一个是处理当前列的栈（colStack）。对于网格中的每个元素，检查它在行和列栈中比它小或相等的元素，如果存在这样的元素，则从栈中移除这些元素并增加答案数组中对应位置的计数。如果在栈中仍然有比当前元素大的元素，则对应位置的计数再增加1。通过这种方式，可以快速地统计每个格子上方和左方能看到的人数。
时间复杂度: O(mn)
空间复杂度: O(m*n)
class Solution:
def seePeople(self, heights: List[List[int]]) -> List[List[int]]:
m, n = len(heights), len(heights[0]) # 获取网格的行数和列数
colStacks = [[] for _ in range(n)] # 初始化每列的栈
rowStack = [] # 初始化行栈
answer = [[0]*n for _ in range(m)] # 初始化答案数组
for r in range(m-1, -1, -1): # 从最后一行开始向上遍历每一行
row, ansRow = heights[r], answer[r] # 获取当前行的高度和答案行
rowStack.clear() # 清空行栈
for c in range(n-1, -1, -1): # 从行的最后一个元素向左遍历
v = row[c] # 当前元素的高度
colStack = colStacks[c] # 当前列的栈
for stack in [rowStack, colStack]: # 遍历行栈和列栈
last = -inf # 初始化上一个见到的元素的高度为负无穷
while stack and stack[-1] <= v: # 弹出所有小于等于当前元素的栈中元素
last = stack.pop() # 更新上一个见到的元素
ansRow[c] += 1 # 更新答案数组
if last < v and stack: # 如果栈顶元素大于当前元素
ansRow[c] += 1 # 答案加1
stack.append(v) # 将当前元素压入栈
return answer # 返回答案数组
Explore
从右下角开始遍历的原因是，这样可以在遍历过程中有效地利用栈来记录和更新每个格子右侧和下方的信息。当从右下角开始向左和向上遍历时，可以保证当前元素的右侧和下方的元素已经被处理过，并且相关信息已经存储在栈中。这种顺序使得算法可以在每一步中有效地使用栈来判断当前元素是否能看到右侧和下方的人，从而减少了重复计算，并提高了算法的效率。
在这个算法中，行栈用于记录当前行中每个元素的高度信息，而列栈则记录当前列中的高度信息。这样，当处理到一个新的元素时，通过查看栈中的元素可以迅速判断出左方和上方有多少个元素是可见的。栈的特性是后进先出，这使得我们可以持续地弹出栈中小于或等于当前元素的高度，这些被弹出的元素代表了它们之前的元素不能看过当前元素继续向左或向上看到更远的元素。每次弹出栈中的元素就相当于确认了一位可见的人，从而快速统计可见人数。
将栈中所有小于等于当前元素的元素弹出的原因是为了维护栈的单调性，确保栈中的元素始终是从栈底到栈顶递减的。这样做的优势在于，当遇到一个新的元素时，可以快速地判断出所有在这个新元素左侧或上方且小于等于它的元素都不能看到更远的地方，因为这个新元素阻挡了它们的视线。此外，这种方法也避免了重复计算，每个元素只在进栈时被计算一次，提高了效率。
如果栈顶元素大于当前元素，说明在当前元素的左侧或上方存在一个更高的元素。这代表当前元素在这个方向上的视线会被栈顶元素阻挡，在这个方向上只能看到这一个更高的人。因此，答案数组在当前位置加1，表示当前元素可以在这个方向上看到一个人（即栈顶元素）。此逻辑确保了只计算直接可见的、即最近的一个比当前元素高的人。