Skip to main content

3904. Smallest Stable Index II

Medium
Description

You are given an integer array nums of length n and an integer k.

For each index i, define its instability score as max(nums[0..i]) - min(nums[i..n - 1]).

In other words:

  • max(nums[0..i]) is the largest value among the elements from index 0 to index i.
  • min(nums[i..n - 1]) is the smallest value among the elements from index i to index n - 1.

An index i is called stable if its instability score is less than or equal to k.

Return the smallest stable index. If no such index exists, return -1.

Example 1:​

Input: nums = [5,0,1,4], k = 3

Output: 3

Explanation:

  • At index 0: The maximum in [5] is 5, and the minimum in [5, 0, 1, 4] is 0, so the instability score is 5 - 0 = 5.
  • At index 1: The maximum in [5, 0] is 5, and the minimum in [0, 1, 4] is 0, so the instability score is 5 - 0 = 5.
  • At index 2: The maximum in [5, 0, 1] is 5, and the minimum in [1, 4] is 1, so the instability score is 5 - 1 = 4.
  • At index 3: The maximum in [5, 0, 1, 4] is 5, and the minimum in [4] is 4, so the instability score is 5 - 4 = 1.
  • This is the first index with an instability score less than or equal to k = 3. Thus, the answer is 3.

Example 2:​

Input: nums = [3,2,1], k = 1

Output: -1

Explanation:

  • At index 0, the instability score is 3 - 1 = 2.
  • At index 1, the instability score is 3 - 1 = 2.
  • At index 2, the instability score is 3 - 1 = 2.
  • None of these values is less than or equal to k = 1, so the answer is -1.

Example 3:​

Input: nums = [0], k = 0

Output: 0

Explanation:

At index 0, the instability score is 0 - 0 = 0, which is less than or equal to k = 0. Therefore, the answer is 0.

Constraints:​

  • 1 <= nums.length <= 10^5
  • 0 <= nums[i] <= 10^9
  • 0 <= k <= 10^9

解題思路​

呈上題 3903. Smallest Stable Index I 的解題思路，若直接用同做法會因為測資較大而超時。

上題的解法是每次都重新計算 maximum 和 minimum，故要提升效率可以從此著手改善。

原本做法
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var firstStableIndex = function (nums, k) {
  for (let i = 0; i < nums.length; i++) {
    const maximum = Math.max(...nums.slice(0, i + 1));
    const minimum = Math.min(...nums.slice(i));

    if (maximum - minimum <= k) return i;
  }

  return -1;
};

首先要改的是 maximum 的部分。
目前是每次都重新計算，但可以用一個變數儲存目前最大值，當遇到更大的數時就更新這個值。

let maximum = 0;

for (let i = 0; i < n; i++) {
  maximum = Math.max(maximum, nums[i]);
}

至於 minimum，可以先建立一個陣列 suffixMin，用來儲存「從目前 index 到最右邊」的最小值。
因為 suffixMin[i] 的計算方式是：

suffixMin[i] = Math.min(nums[i], suffixMin[i + 1]);

也就是說，suffixMin[i] 的計算需要先知道右邊的 suffixMin[i + 1]。
因此我們必須先從最右邊開始計算，再一路往左建立 suffixMin。

接著才能依序計算 suffixMin[n - 2]、suffixMin[n - 3]……直到 suffixMin[0]。
如果從左到右計算，就會發現當我們要計算 suffixMin[i] 時，右邊的 suffixMin[i + 1] 還沒有被計算出來，因此無法使用這個公式。

const n = nums.length;

const suffixMin = new Array(n); // 直接建立一個長度為 n 的陣列
suffixMin[n - 1] = nums[n - 1]; // 最右邊的 suffixMin[n - 1] 沒有右邊的元素，所以它的最小值就是自己

// 從右往左建立 suffixMin
for (let i = n - 2; i >= 0; i--) {
  suffixMin[i] = Math.min(nums[i], suffixMin[i + 1]); // 當前數字和右邊的最小值比較，取較小的
}

所以整體的邏輯就是先算好所有的 minimum，再從左往右算 maximum。 最後才能計算：

maximum - suffixMin[i];

也就是題目要求的：左邊最大值 - 右邊最小值

心得​

豪難，看了好久才稍微理解：（