1. 문제 소개

Constraints:

• 1 <= n == nums.length <= 105
• 0 <= nums[i] <= 105

3542. Minimum Operations to Convert All Elements to Zero

2. 나의 풀이

풀이는 다음의 이미지를 참고하며 풀었다.
시간복잡도는 $O(log n)$이다.

class Solution:
    def minOperations(self, nums: List[int]) -> int:
        stack = []                 # 단조 증가 스택(현재 '활성 높이층' 저장)
        ans = 0                    # 최소 연산 횟수 누적
        for num in nums:           # 왼쪽에서 오른쪽으로 순회
            while stack and stack[-1] > num:  # 현재 높이보다 큰 층은 접어서 제거
                stack.pop()
            if num == 0:           # 0은 이미 제거된 상태이므로 스킵
                continue
            if not stack or stack[-1] < num:  # 새 높이층 시작 시에만 연산 +1
                ans += 1
                stack.append(num)  # 현재 높이를 활성 층으로 등록
        return ans                 # 전체 최소 연산 횟수 반환

3. 다른 풀이

가장 짧은 시간이 걸린 풀이를 가져왔다.

class Solution:
    def minOperations(self, nums):
        stack = [0] * (len(nums) + 1)
        top = 0
        ans = 0

        for num in nums:
            while stack[top] > num:
                top -= 1
                ans += 1
            if stack[top] != num:
                top += 1
                stack[top] = num

        return ans + top

4. 결론

아직 모르는 것이 많아 잘 풀지 못해 속상하다.