[leetcode]1906. Minimum Absolute Difference Queries

Mayton·2022년 8월 6일

Coding-Test

목록 보기

21/37

문제

The minimum absolute difference of an array a is defined as the minimum value of |a[i] - a[j]|, where 0 <= i < j < a.length and a[i] != a[j]. If all elements of a are the same, the minimum absolute difference is -1.

For example, the minimum absolute difference of the array [5,2,3,7,2] is |2 - 3| = 1. Note that it is not 0 because a[i] and a[j] must be different.
You are given an integer array nums and the array queries where queries[i] = [li, ri]. For each query i, compute the minimum absolute difference of the subarray nums[li...ri] containing the elements of nums between the 0-based indices li and ri (inclusive).

Return an array ans where ans[i] is the answer to the ith query.

A subarray is a contiguous sequence of elements in an array.

The value of |x| is defined as:

x if x >= 0.
-x if x < 0.

예시

Example 1:

- Input: nums = [1,3,4,8], queries = [[0,1],[1,2],[2,3],[0,3]]
- Output: [2,1,4,1]
- Explanation: The queries are processed as follows:
	- queries[0] = [0,1]: The subarray is [1,3] and the minimum absolute difference is |1-3| = 2.
	- queries[1] = [1,2]: The subarray is [3,4] and the minimum absolute difference is |3-4| = 1.
	- queries[2] = [2,3]: The subarray is [4,8] and the minimum absolute difference is |4-8| = 4.
	- queries[3] = [0,3]: The subarray is [1,3,4,8] and the minimum absolute difference is |3-4| = 1.

Example 2:

 -Input: nums = [4,5,2,2,7,10], queries = [[2,3],[0,2],[0,5],[3,5]]
- Output: [-1,1,1,3]
- Explanation: The queries are processed as follows:
	- queries[0] = [2,3]: The subarray is [2,2] and the minimum absolute difference is -1 because all the elements are the same.
	- queries[1] = [0,2]: The subarray is [4,5,2] and the minimum absolute difference is |4-5| = 1.
	- queries[2] = [0,5]: The subarray is [4,5,2,2,7,10] and the minimum absolute difference is |4-5| = 1.
	- queries[3] = [3,5]: The subarray is [2,7,10] and the minimum absolute difference is |7-10| = 3.

제한사항

2 <= nums.length <= 105
1 <= nums[i] <= 100
1 <= queries.length <= 2 * 104
0 <= li < ri < nums.length

풀이


/**
 * @param {number[]} nums
 * @param {number[][]} queries
 * @return {number[]}
 */
 var minDifference = function(nums, queries) {
  const res = Array.from(nums.length)
  for(let i=0 ;i<queries.length;i++){
      const [start,end]= queries[i];
      const array= nums.slice(start, end+1).sort((a,b)=>a-b)
      let diff=Infinity;
      for(let i=1;i<array.length;i++){
          const tempDiff= Math.abs(array[i]-array[i-1]);
          if(tempDiff==0)continue;
          diff=diff>tempDiff?tempDiff :diff;
      }
      if(diff==Infinity){
      res[i]=-1    
      }else{
          res[i]=diff
      }
  }
  
  return res
}

queries에 있는 array를 정렬해 놓고, 다음 value와의 차가 제일 작은 것이 res의 원소로 정해서 res를 출력했으나, 결과는 Time Limit exceed였다. query.length가 2**104만큼 커질 수 있는 상황이기 때문에, query.length내에는 그에 준하는 길이의 for문을 수행해서는 안되는 것이었다.

풀이 2

/**
 * @param {number[]} nums
 * @param {number[][]} queries
 * @return {number[]}
 */
var minDifference = function (nums, queries) {
  const MAX = Number.MAX_SAFE_INTEGER;
  const n = nums.length;
  const prefixSums = [];

  for (let i = 0; i <= n; ++i) {
    const num = nums[i];

    if (i === 0) {
      prefixSums[0] = new Array(101).fill(0);
    } else {
      prefixSums[i] = [...prefixSums[i - 1]];
      ++prefixSums[i][nums[i - 1]];
    }
  }
  //최대 길이가 101이기 때문에, sliding Windows처럼 앞에서부터 첫번째, 두번째, 세번째의 원소들을 다 짤라서 prefixSums에 넣어놓았다.

  const res = [];

  for (let i = 0; i < queries.length; ++i) {
    const [left, right] = queries[i];

    const start = prefixSums[left];
    const end = prefixSums[right + 1];

    const intersect = new Array(101).fill(0);

    for (let i = 0; i < 101; ++i) {
      intersect[i] = end[i] - start[i];
    }

    let last = -1;
    let minDiff = MAX;

    for (let i = 1; i <= 100; ++i) {
      if (intersect[i] === 0) continue;

      if (last == -1) {
        //첫 원소를 구분
        last = i;
      } else {
        //원소가 몇인지 구분
        //어짜피 가장 옆에있는 값끼리 차를 구해야지, 안그러면
        const diff = i - last;

        minDiff = Math.min(minDiff, diff);

        last = i;
      }
    }

    if (minDiff === MAX) res[i] = -1;
    else res[i] = minDiff;
  }

  return res;
};