[leetcode][795] Number of Subarrays with Bounded Maximum

문제 : https://leetcode.com/problems/number-of-subarrays-with-bounded-maximum/

---

양수 배열 nums, 두 개의 양수 left, right 가 입력으로 주어진다.

nums 배열의 하위배열(연속적인 부분배열. 비어있지 않음)의 최대 원소가 left 이상, right 이하인 하위배열들의 수를 구해라.

---

재미있는 투포인터문제~

nums를 처음부터 탐색하면서 정답이 될 수 있는 범위를 l, r 변수에 저장한다. (l = 왼쪽, r = 오른쪽 인덱스)

 

l 변수는 nums[i]가 부분배열에 포함될 때 정답이 절대 불가능할 때 갱신한다.

최대값만 left, right를 비교하기 때문에 정답이 절대 불가능한 경우는 nums[i]가 right보다 큰 경우이다.

 

r 변수는 nums[i]만 부분배열에 포함될 때 정답이 가능한경우 있을 때 갱신한다. 

정답이 가능한 경우는 nums[i]가 left 이상 right 이하인 경우이다. 

 

r이 l보다 크거나 같을 때, l~r 범위 길이를 정답에 더해준다.

l~r 범위는 nums[i]를 부분배열에 포함시키면서 만들 수 있는 정답부분배열들의 개수이다.

 

[그림 1]

nums = [2,1,3,4,3].  left = 2.  right = 3.

이 입력값일 때, 변수들은 [그림 1]과 같이 갱신된다.

인덱스 1, 2일 때 answer가 될 수 있는 부분배열들의 예시를 보면 r 변수가 갱신되는 조건을 이해하는데 도움이 될 것이다.

 

시간복잡도는 O(|nums|).

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/795.%20Number%20of%20Subarrays%20with%20Bounded%20Maximum.cpp