📘 題目敘述
給定一個整數陣列 nums，長度為 n，以及一個整數 k。
對每個索引 i，定義它的 instability score 為：
max(nums[0..i]) - min(nums[i..n - 1])
也就是說：
max(nums[0..i])是從索引0到i之間的最大值min(nums[i..n - 1])是從索引i到n - 1之間的最小值
如果某個索引 i 的 instability score 小於等於 k，那麼這個索引就叫做 stable。
請回傳最小的 stable index。
如果不存在，回傳 -1。
條件限制
1 <= nums.length <= 1000 <= nums[i] <= 10^90 <= k <= 10^9
🧠 解題思路
我這題的想法是先把每個位置需要用到的：
- 左側前綴最大值
- 右側後綴最小值
都先預處理出來。
因為題目對每個 i 都要算：
max(nums[0..i])min(nums[i..n - 1])
如果每次都現場重新掃一遍，雖然這題資料小也能過，但我這份寫法是直接先把這兩種資訊存起來。
所以我開了兩個陣列：
nmax[i]：表示nums[0..i]的最大值nmin[i]：表示nums[i..n - 1]的最小值
這樣之後只要對每個位置直接算：
nmax[j] - nmin[j]
就能知道這個索引是不是 stable。
接著從小到大找第一個符合條件的位置即可。
所有變數
n：陣列長度nmax：prefix maximum，nmax[i]表示從0到i的最大值nmin：suffix minimum，nmin[i]表示從i到n - 1的最小值
🪜 主要流程步驟
1. 先建立 prefix maximum 和 suffix minimum 陣列
我先開兩個陣列，它們分別拿來記錄：
- 每個位置往左看到的最大值
- 每個位置往右看到的最小值
這樣後面每個索引的 instability score 就可以直接查表，不用重算。
2. 初始化最左邊和最右邊的基準值
因為 prefix maximum 是從左往右推，所以最左邊先設成：
nmax[0] = nums[0];而 suffix minimum 是從右往左推，所以最右邊先設成：
nmin[n - 1] = nums[n - 1];這兩個位置都是各自方向上的起點。
3. 一次迴圈同時更新 prefix maximum 和 suffix minimum
接著我用一個迴圈，同時更新這兩個陣列：
前半段：
nmax[i] = max(nmax[i - 1], nums[i]);意思是：
nmax[i - 1]已經知道0..i-1的最大值- 再跟
nums[i]比一下 - 就能得到
0..i的最大值
後半段：
nmin[n - 1 - i] = min(nmin[n - i], nums[n - 1 - i]);則是在倒著更新 suffix minimum。
意思是：
nmin[n - i]已經知道右邊那段的最小值- 再和目前這格
nums[n - 1 - i]比較 - 就能得到從目前位置到最右邊的最小值
所以這一輪做完後，nmax 和 nmin 兩個陣列都會完整建立起來。
4. 從左到右找第一個 stable index
當 nmax 和 nmin 都準備好之後，
我就從左到右掃每個索引 j，直接檢查這裡的：
nmax[j]就是max(nums[0..j])nmin[j]就是min(nums[j..n-1])
所以兩者相減，就是題目定義的 instability score。
而題目要的是最小的 stable index，
所以我只要從左到右第一個找到符合條件的位置，就可以立刻回傳。
5. 如果全部都不符合，就回傳 `-1`
如果整個掃完都沒有任何索引滿足：
nmax[j] - nmin[j] <= k那就代表根本不存在 stable index。
最後直接回傳 -1。
⏱️ 複雜度
設 n = nums.length。
- 時間複雜度：
O(n)
我先掃一次建立 nmax 和 nmin，再掃一次找答案。
- 空間複雜度：
O(n)
我另外使用了兩個長度為 n 的陣列。
💻 程式碼實作
class Solution {
public:
int firstStableIndex(vector<int>& nums, int k) {
int n = nums.size();
vector<int> nmax(n);
vector<int> nmin(n);
nmax[0] = nums[0];
nmin[n - 1] = nums[n - 1];
for (int i = 1; i < n; i++) {
nmax[i] = max(nmax[i - 1], nums[i]);
nmin[n - 1 - i] = min(nmin[n - i], nums[n - 1 - i]);
}
for (int j = 0; j < n; j++) {
if (nmax[j] - nmin[j] <= k) {
return j;
}
}
return -1;
}
};🔗 題目連結
https://leetcode.com/contest/weekly-contest-498/problems/smallest-stable-index-i/