1918. Maximum Score of a Good Subarray

좋은 부분 배열은 인덱스 k를 반드시 포함해야 하므로, k를 중심으로 양쪽으로 확장하는 투 포인터를 이용하기로 했다. 중요한 부분은 포인터를 움직이는 기준이었는데, 점수 = min(부분배열) * 길이이므로, 현재 min을 최대한 높게 유지하는 방향으로 포인터를 이동시켰다. 범위의 최솟값이 최대한 변하지 않으려면 작은 것을 변화시키는 것보다는 큰 것을 변화시키는 것이 유리하다. (작은 것이 변했는데 운이 나쁘게 더 작은 것이 나오면 min이 더 작아질 수 있다.) 따라서 left의 왼쪽(left-1)과 right의 오른쪽(right+1) 을 비교해서, 더 큰 값 쪽으로 포인터를 이동시켰다.

코드

function maximumScore(nums: number[], k: number): number {
  let left = k,
    right = k;
  let curMin = nums[k];
  let maxScore = nums[k];

  while (left > 0 || right < nums.length - 1) {
    if (left === 0) right++;
    else if (right === nums.length - 1) left--;
    else if (nums[left - 1] >= nums[right + 1]) left--;
    else right++;

    curMin = Math.min(curMin, nums[left], nums[right]);
    maxScore = Math.max(maxScore, curMin * (right - left + 1));
  }

  return maxScore;
}

시간 / 공간 복잡도

시간 복잡도: O(n) — 배열 전체를 한 번 순회
공간 복잡도: O(1) — 포인터 변수만 사용

1918. Maximum Score of a Good Subarray

문제

풀이

아이디어

코드

시간 / 공간 복잡도