problem link : https://leetcode.com/problems/number-of-visible-people-in-a-queue/ approach for the above mentioned question when duplicates are allowed
eg test case : 11 6 7 5 11 11 o/p : 3 2 2 1 1 0
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | ecnerwala | 3649 |
| 2 | Benq | 3581 |
| 3 | orzdevinwang | 3570 |
| 4 | Geothermal | 3569 |
| 4 | cnnfls_csy | 3569 |
| 6 | tourist | 3565 |
| 7 | maroonrk | 3531 |
| 8 | Radewoosh | 3521 |
| 9 | Um_nik | 3482 |
| 10 | jiangly | 3468 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | awoo | 164 |
| 3 | adamant | 161 |
| 4 | TheScrasse | 159 |
| 5 | nor | 158 |
| 6 | maroonrk | 156 |
| 7 | -is-this-fft- | 152 |
| 8 | SecondThread | 147 |
| 9 | orz | 146 |
| 10 | pajenegod | 145 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 26.04.2024 22:05:37 (g1).
Десктопная версия, переключиться на мобильную.
При поддержке
Looks solvable with an increasing stack
ok
I looked at the question again and it's supposed to be a decreasing stack not an increasing stack. My solution for original qn (in Python)
class Solution:
____def canSeePersonsCount(self, heights: List[int]) -> List[int]:
________a = heights
________n = len(a)
________stack = [] # decreasing stack
________ans = [-1] * n
________for i in range(n — 1, -1, -1):
____________cnt = 0
____________while len(stack) > 0 and a[stack[-1]] < a[i]:
________________cnt += 1
________________stack.pop()
____________if len(stack) > 0:
________________ans[i] = cnt + 1
____________else:
________________ans[i] = cnt
____________stack.append(i)
________return ans
If you want to work with duplicated elements, at a[i] you need to add an additional factor k — 1 if the last element in stack after popping is also a[i]. k is the number of elements in the stack equivalent to a[i], which you can binary search since the stack is decreasing.
Sorry my described method for duplicate cases won't work. You need to handle cases like 5 3 3 4 4 3 3 4 4 5. Maybe a decreasing stack storing [value, counts] might work. You'll need to figure out how to merge the counts for repeated elements and to add the counts when popping off the stack.
Hey Sandeep,
What is your solution for the case when all heights are different? I think [this solution] for example, (https://leetcode.com/problems/number-of-visible-people-in-a-queue/discuss/1961776/Number-of-Visible-People-in-a-Queue) should work in both cases.
It is Not working , when duplicates heights are given :|
I think it should work. The person 'i' cannot see anything beyond person 'j' if heights[i] <= heights[j]. The expected result for your example is '3 1 2 1 1 0'. I think you have a typo for the second number, right?
Notice, that LeetCode rejects inputs with repeated elements, but this does not mean the solution does not work.