[백준] 17298번: 오큰수

https://www.acmicpc.net/problem/17298

initial

very similar to previous qustions on stack but

1) be careful where and when to use break. Normally if you have gotten what you need out of your main for loop logic like placing a value in answer list, then you break

2) Here we initialise answer with -1 values because elements at the start, end and anywhere in the lst can have values on the right that are smaller than itself. Since our main logic cannot take care of this case, we just initialise as -1.

solution

from collections import deque

n = int(input())
lst = list(map(int,input().split()))
stack = deque()
ans = [-1 for _ in range(n)]

for i in range(len(lst)-1,-1,-1):
    while stack:
        if lst[i]<stack[-1]:
            ans[i]=stack[-1]
            break
        else:
            stack.pop()
    stack.append(lst[i])
print(*ans)

complexity

The provided code is used to find the nearest greater element to the right of each element in the input list using a stack-based approach. Let's analyze the time and space complexity of this code:

1. Time Complexity:

   • The code uses a loop that iterates through the input list in reverse order (for i in range(len(lst)-1,-1,-1)). This loop iterates through all n elements, so it contributes O(n) to the time complexity.

   • Inside the loop, there's another while loop that iterates through the elements in the stack. In the worst case, the while loop can iterate through all elements in the stack before breaking out. In such a case, the inner while loop would also contribute O(n) to the time complexity.

   Therefore, the overall time complexity of the code is O(n).

2. Space Complexity:

   • The code uses a stack (stack) to store elements. The maximum number of elements that can be in the stack is bounded by n (the number of elements in the input list).

   • The ans list, used to store the results, has a length of n.

   Therefore, the space complexity of the code is O(n).

In summary, the code has a time complexity of O(n) and a space complexity of O(n), where n is the number of elements in the input list.