0ms C++ Py3 |Suffix MIN與Prefix MAX解Leetcode 3903, 3904 Smallest Stable Index

0ms C++ Py3 Suffix MIN與Prefix MAX解Leetcode 3903, 3904  Smallest Stable Index

使用一個名為 suf 的陣列來記錄字尾最小值（suffix min）。

接著進行動態Prefix MAX（字首最大值）的計算，以找出何時滿足Max-suf[i] leq k！

[Py3  code請進]

在 Python 實作中，使用 itertools.accumulate 處理 Suffix MIN 時需要特別小心。因為我們是先透過 nums[::-1] 將陣列反轉後才進行累計運算，所以得到的結果必須再次使用 [::-1] 轉回來。這樣在後續與 Prefix MAX 進行比對時，enumerate 產生的索引 i 才能正確對應到原始陣列的位置，確保邏輯萬無一失！

[codes on Leetcode 3903]https://leetcode.com/problems/smallest-stable-index-i/solutions/8500415/suffix-min-running-prefix-max-same-as-lc-1a6e/

-----

Use an array suf to hold the suffix min.

Proceed an running prefix Max to find when Max-suf[i] leq k!

In the Python implementation, be extra careful when using itertools.accumulate for Suffix MIN. Since we reverse the array using nums[::-1] before performing the accumulation, the result must be reversed again with [::-1]. This ensures that when we compare it with the Prefix MAX, the index i from enumerate correctly aligns with the original array positions, keeping the logic perfectly consistent!

English timestamps for the key sections:

00:00 - Introduction to Leetcode 3903 & 3904

00:32 - Performance Results (0ms C++)

00:44 - Problem Analysis & Constraints

01:03 - Defining Instability Score & Stable Index

02:26 - Algorithmic Strategy: Suffix MIN & Prefix MAX

03:12 - Example Walkthrough (Example 1)

04:05 - Example Walkthrough (Example 2)

04:45 - Example Walkthrough (Example 3)

05:07 - C++ Implementation Details (3903)

07:12 - Python 3 Implementation using accumulate & Slicing

09:11 - Optimizing for Large Constraints (3904)

10:11 - Conclusion

class Solution:
    def firstStableIndex(self, nums: list[int], k: int) -> int:
        xMax=-1
        for i, s in enumerate(list(accumulate(nums[::-1], min))[::-1]):
            xMax=max(xMax, nums[i])
            if xMax-s<=k: return i
        return -1