Блог пользователя sandeepgogarla61

can someone help me out with this leetcode 1944 problem
Автор sandeepgogarla61, история, 2 года назад, По-английски

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

  • Проголосовать: нравится
  • -11
  • Проголосовать: не нравится

»
2 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Looks solvable with an increasing stack

→ Ответить
  • »
    »
    2 года назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    ok

    → Ответить
    • »
      »
      »
      2 года назад, # ^ |
      ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      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)

      Code:

      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.

      → Ответить
      • »
        »
        »
        »
        2 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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.

        → Ответить
»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    It is Not working , when duplicates heights are given :|

    → Ответить
    • »
      »
      »
      2 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

      → Ответить