2751. Robot Collisions
## 思路
Sort by position
maintain一個往右走的stack (to_right)
如果遇到往左走的就比較大小, 照三種情形更新healths
最後回傳所有 >0 的health
## Complexity
Time Complexity: O(N logN) # sort, 用counting sort O(N)
Space Complexity: O(N) # stack
## Code
```python
class Solution:
def survivedRobotsHealths(self, positions: List[int], healths: List[int],
directions: str) -> List[int]:
n = len(positions)
heap = []
for idx, (pos, d) in enumerate(zip(positions, directions)):
heapq.heappush(heap, (pos, d, idx))
to_right = []
while heap:
pos, d, idx = heapq.heappop(heap)
if d == 'R':
to_right.append(idx)
continue
while to_right and healths[idx]:
if healths[to_right[-1]] > healths[idx]:
healths[to_right[-1]] -= 1
healths[idx] = 0
break
elif healths[to_right[-1]] == healths[idx]:
healths[idx] = healths[to_right.pop()] = 0
else:
healths[idx] -= 1
healths[to_right.pop()] = 0
return [health for health in healths if health]
```
太習慣直接用heap..
改用indices.sort直接快200ms:
indices = list(range(n))
indices.sort(key=lambda x: positions[x])
for idx in indices:

你好 新版友 請發錢

錢

大師 錢

不是應該反過來給我錢嗎QQ

看來你不懂邊板 錢

大師

前

大師

外來種 錢