leetcode 2104. Sum of Subarray Ranges

문제 요약

 

주어진 nums의 모든 subarray들의 (최대값 - 최소값) 들의 합을 구하는 문제였습니다. 이전의 풀어본 leetcode 907가 subarray의 최소값의 합이였기 때문에 이 문제를 기억하여 대략적으로 방향이 나올 수 있었습니다.

2023.05.01 - [Algorithm/problem solving] - leetcode 907. Sum of Subarray Minimums

leetcode 907. Sum of Subarray Minimums

 

해결

Increasing monotonic stack과 Decreasing monotonic stack 2개를 같이 이용하여 해결할 수 있었습니다. 각각의 monotonic stack에서 상황에 따라 계산하는 방법은 위에 첨부된 leetcode 907 풀이한 것으로 대신하겠습니다. 이 문제의 특정 nums에 대한 시뮬레이션은 아래와 같습니다.

01234567891011121314

Increasing monotonic stack 산출물은 min값을, Decreasing monotonic stack 산출물은 max값을 의미하고 있으므로 최종 계산은 Σ(Decreasing monotonic stack 산출물) - Σ(Increasing monotonic stack 산출물) 을 구해주면 되겠습니다.

 

교훈

이전에 비슷한 문제를 풀고 비슷하게 해결했지만 머리 속으로 잘 떠올려지지 않았습니다. 그럴때면 위와 같이 슬라이드로 하나하나 그려보자는 교훈을 얻었습니다. 확실히 그 과정이 이해가 잘 됩니다. 나중에 까먹더라도 빠르게 떠올릴 수 있을 것 같습니다.