Skip to content

962.maximum-width-ramp.md

Latest commit

 

History

History
369 lines (286 loc) · 14.1 KB

962.maximum-width-ramp.md

File metadata and controls

369 lines (286 loc) · 14.1 KB
Raw

962. Maximum Width Ramp

Sorting + Enumeration

觀察與瓶頸

原題目的條件有兩個：

  • 條件 A：i < j (位置條件)
  • 條件 B：nums[i] <= nums[j] (數值條件)

在我們原本的推導中，我們最怕的就是條件 B，因為數值上上下下（下凹陷阱），導致我們不知道該不該配對。

抽象化推導

  • 如果我們讓條件 B「絕對成立」，是不是就不用煩惱了？怎麼讓數值條件絕對成立？答案是：把整個陣列依照「數值大小」排序，那因為我們要用位置來算寬度，所以我們需要把原始位置綁在一起後才排序。
  • 對於排序後的任何兩個元素，我們已經 100% 確定 X.value <= Y.value，這時候，原本困難的條件 B 消失了，問題瞬間降維成極度簡單的條件 A：「對於現在掃到的元素 Y (原始位置為 Y.index），在它前面出現過的所有元素中，最小的原始位置是多少？」 只要拿 Y.index - 最小的原始位置，就是合法的 Ramp 寬度！

There are two rules to form a valid ramp:

  1. Value Rule: nums[i] <= nums[j].
  2. Index Rule: i < j, and try to maximize the width j - i.

We can use sorting to solve the Value Rule first, so we only have to care about the Index Rule after that.

Step 1: Solve Value Rule by Sorting

We need to sort the value, but meanwhile we also need to keep track of the original index to calculate the width. So we can create an array of indices and sort the indices by its value.

value = [7, 6, 5, 8]
index = [0, 1, 2, 3]

// After sorting
value = [5, 6, 7, 8]
index = [2, 1, 0, 3]

Step 2: Solve Index Rule by Enumeration

After sorting and when we iterate from left to right, we know that the current number is greater than or equal to all the previous numbers, so all later number will be a valid ending candidate.

To find the maximum width, we iterate the sorted index as the ending index j, and keep track of the minimum starting index i we've seen so far. The width is j - i, and we update the maximum width accordingly.

fun maxWidthRamp(nums: IntArray): Int {
    val n = nums.size
    val index = IntArray(n)
    for (i in nums.indices) {
        index[i] = i
    }
    val sortedIndex = index.sortedBy { nums[it] }
    var minIndex = sortedIndex.first()
    var maxWidth = 0
    for (i in 1 until n) {
        maxWidth = maxOf(maxWidth, sortedIndex[i] - minIndex)
        minIndex = minOf(minIndex, sortedIndex[i])
    }
    return maxWidth
}
  • Time Complexity: O(n log n) for sorting.
  • Space Complexity: O(n) for the sorted index.

Monotonic Stack

Abstraction

  • Among all the pairs of i and j where i < j and nums[i] ≤ nums[j], find the maximum difference between i and j.

  • For each i, find the first greater (or equal) element from right to left.

_, _, i, _, _, _, x1, _, _, x2, _, _
                            <-----

nums[i] <= nums[x2] // Find it, stop for index i
nums[i] <= nums[x1] // We don't need to check

Brute Force

  • Forward: Iterate each i, for each i:

    • Iterate each j from end to i + 1: If we find the nums[i] ≤ nums[j], update the answer and break the inner loop.
fun bruteForce(nums: IntArray): Int {
    var maxWidth = 0
    for (i in nums.indices) {
        for (j in nums.size - 1 downTo i + 1) {
            if (nums[i] <= nums[j]) {
                maxWidth = maxOf(maxWidth, j - i)
                break
            }
        }
    }
    return maxWidth
}

The following brute force is logically correct, but it’s not based on the outcome of abstraction, it’s hard to analyze the bottleneck, we should not use it.

  • Forward: Iterate each i, for each i:

    • Iterate each j from i + 1 to end: Find the greater value: update the answer.

  • Backward: Iterate each j, for each j:

    • Iterate each i from 0 to j - 1: find smaller value and update the index difference.
fun bruteForce1(nums: IntArray): Int {
    var maxWidth = 0
    for (i in nums.indices) {
        for (j in i + 1 until nums.size) {
            if (nums[i] <= nums[j]) {
                maxWidth = maxOf(maxWidth, j - i)
            }
        }
    }
    return maxWidth
}

private fun bruteForce2(nums: IntArray): Int {
    var maxWidth = 0
    for (j in nums.indices) {
        for (i in 0 until j) {
            if (nums[i] <= nums[j]) {
                maxWidth = maxOf(maxWidth, j - i)
            }
        }
    }
    return maxWidth
}

  • Time complexity: O(n^2)

  • Space complexity: O(1)

Bottleneck

以抽象化「遍歷每個 i，從右往左找第一個大於等於的元素」所寫出來的暴力解：「外迴圈遍歷每個 i 當作起點，然後內迴圈從右走到左，找到就跳出。」

這個瓶頸不在內迴圈 (找到就跳出)，而是在外迴圈：遍歷每個可能的起始點，問題是它慢在哪呢？他是慢在盲目地把每個 i 當作起始點去看，那有沒有什麼起始點我們是不必要看的嗎？

舉例說明

假個我們有兩個 A, B 數值在競爭可能的起始點：

_, _, 3, _, _, _, 6, _, _, _, 7
      A           B           X
      |-----------------------|
                  |-----------|
// Which one is the answer, A or B?

_, _, 3, _, _, _, 6, _, _, _, 4
      A           B           X

我們在後面遇到 X，兩種情況：

  1. 如果 X = 7, 那 A 和 B 誰可以配對嗎？誰會是答案？

    → A, B 都可以配對，但是 A 是更寬才是答案。

  2. 那如果 X = 4, 那 A 和 B 誰可以配對嗎？誰會是答案？

    → 只有 A 可以配對，所以只有 A 是答案。

在任意時刻，B (位置比較靠右，數字又比較大) 無法提供比 A 更寬的答案，在未來能找到大於等於 B 的機率又更低，所以我們應該直接捨棄。

證明

我們用第一性原理來證明一下，我們就用 i 和 i + 1 作為起點相互比較一下他們的寬度 j - 起點 要更優。一個起點要贏的話，有兩個競爭力的指標：

  1. 位置：越靠左越好。

  2. 數值：越小越好，越容易在右邊找到大於等於的值。

以上述兩個指標來看 i vs i + 1，i + 1 已經在位置上輸了，那麼只有在「數值」上有贏過 i 才有機會成爲更優的寬度，也就是 nums[i] > nums[i + 1]。

那這就代表如果 nums[i] ≤ nums[i + 1] 的時候，以 i + 1 為起點是不必要的效能瓶頸。

Pattern Recognition

以上述效能瓶頸分析來看，結論就是我們從左往右挑選起始點時，我們只會挑選越來越小的數值當起始點，也就是起點們是呈現一個「嚴格遞減」的數列，只要是下一個數字能比目前起點都小的話，那麼那些起點都可以捨棄了，這就推導出我們要用 Monotonic Stack 找「嚴格遞減」的起點數列。

這邊我們不使用常見的 Monotonic Stack 模板，這模板是在找右邊第一個較大的元素：

val stack = ArrayDeque<Int>()
for (i in nums.indices) {
    while (stack.isNotEmpty() && nums[stack.last()] < nums[i]) {
        val idx = stack.removeLast()
        // nums[idx] → next greater = nums[i]
    }
    stack.addLast(i)
}

然而，這題只需要找出「嚴格遞減」的起點數列就好，所以我們先迭代一次建立這數列。

for (i in nums.indices) {
    if (stack.isEmpty() || (stack.isNotEmpty() && nums[stack.last()] > nums[i])) {
        stack.addLast(i)
    }
}

然後再開始從右邊往左找有效的終點 j：

  • 針對每個 j，我們嘗試跟目前的起點序列 stack.peek() 配對，直到無法配對為止。因為 j 可以能是一個很大的數字，能夠很多起點配對，所以我們就貪心的去配對。
stack = [6, 4, 3, 1]  nums[j] = 5
                  |-------------|
               |----------------|
            |-------------------|
  • 起點 i 配對完之後，我們就會把它「退休」pop()，因為針對相同的 i，j 後續只會往左走，寬度只會越小，就不可能是較優的答案。
 6, 0, _, _, 1, 5
    i-----------j    // valid, final answer
            <--
    i--------j       // valid, but narrower
    ...    
fun monotonicStack(nums: IntArray): Int {
    // Index, decreasing stack, store the valid starting element.
    val stack = ArrayDeque<Int>()

    // Find the valid starting `i`
    for (i in nums.indices) {
        if (stack.isEmpty() || 
            (stack.isNotEmpty() && nums[stack.last()] > nums[i])) stack.addLast(i)
    }

    var maxWidth = 0
    // Iterate from right to left backward to find the valid ending `j`
    for (j in nums.size - 1 downTo 0) {
        // No any valid starting index.
        if (stack.isEmpty()) break
        while (stack.isNotEmpty() && nums[stack.last()] <= nums[j]) {
            val i = stack.removeLast()
            maxWidth = maxOf(maxWidth, j - i)
        }
    }
    return maxWidth
}
  • Time Complexity: O(n). Each index is pushed and popped at most once.
  • Space Complexity: O(n) for the stack.

Two Pointers

當我們看到「尋找最大區間 / 最長子陣列」這種關鍵字時，大腦的第一反應通常是Sliding Window（滑動窗口 / 同向雙指標）。問題是，當 j 往右走擴展窗口時，如果遇到較小的數字，那應該是縮點左窗口還是繼續擴展？ 例如 [6, 0, 8, ...]，當 j 指向 0 的時候，這時候 nums[i] > nums[j]：

6, 0, 8
i ->    // shrink? or
   j -> // expand?

這情況猶豫「我到底該不該把 i 往右移？如果 j 的後面還有大於等於 6 的數字，我就應該死守著 i；如果 j 的後面全部都是小於 6 的數字，那我就應該果斷放棄 i。」

在這種情況下，我們就會想到「如果我預先知道 j 往右走之後的數字是什麼，我就知道我該不該放棄 i 了」，所以，我們渴望的超能力是：「站在目前的 j，我想要知道從 j 一直到陣列盡頭，出現過的『最大數字』是多少？是否有出現大於等於 nums[i] 的數字？」

  • 有的話，目前 i 就應該先留著。
6, 0, 8
i 
   j // There is 8 later, we should keep i and try to expand j to find 8.
  • 沒有的話，i 就沒有用了，應該果斷放棄。
6, 0, 5
i ->
   j

所以，我們可以先預處理來知道每個位置 j 一直到盡頭出現的最大數字。

To maximum the width j - i, we want two things:

  1. The smallest number before (Easy to find the larger number later)
  2. The largest number after (Easy to find the smaller number earlier)

We can pre-compute the two information for every single index:

  • Prefix minimum: The minimum value we've seen so far from the left side. This answers the question: "If I am forced to pick a starting number before/at index i, what is the smallest (best) choice?"
A = [6, 0, 8, 2, 1, 5]
--> min
     6  0  0  0  0  0
  • Suffix maximum: The maximum value we've seen so far from the right side. This answers the question: "If I am forced to pick a ending number after/at index j, what is the largest (best) choice?"
A = [6, 0, 8, 2, 1, 5]
              max <--
     8  8  8  5  5  5

How to Move Pointers?

Because both the prefix minimum and suffix maximum are in descending order (when reading from left to right), then we can use two pointers to find the maximum ramp.

  • left: Scan the prefix minimum to look for starting candidate.
  • right: Scan the suffix maximum to look for ending candidate.

We iterate each index, and for each left pointer, we try to find the maximum right pointer such that prefix minimum <= suffix maximum:

  • If minBefore[left] > maxAfter[right], the starting candidate is too large to match the ending candidate.
    • We need smaller starting candidates, so we move left + 1 because the prefix minimum gets same or smaller as we move right.
    • Moving right + 1 will gets same or smaller suffix maximum as well, and minBefore[left] > maxAfter[right], smaller maxAfter[right] makes the situation worse.
  • If minBefore[left] <= maxAfter[right], it's a match.
    • Update the maximum width with right - left accordingly.
    • Move the right + 1 to get a wider ramp.
    • Why not moving the left? Because moving left gets the narrower ramp. We know moving right will make maxAfter[right] smaller, but it's the only direction that increase the width.
A = [6, 0, 8, 2, 1, 5]
     6  0  0  0  0  0   // prefix minimum
     8  8  8  5  5  5   // suffix maximum
     L
     |-----R            // The longest ramp starting from `6`
           
// Next iteration
        L
        |-----------R   // The longest ramp starting from `0`, the final answer

Why it Works?

The monotonicity provides the predictability, we know exactly what happens when we move the pointers:

  1. Moving left + 1: The prefix minimum will stay the same or decrease, which makes it easier to find a matching ending candidate.
  2. Moving right + 1: The suffix maximum will stay the same or decrease, which makes it harder to find a matching starting candidate, but it makes a potential wider ramp.

We never need to move a pointer backwards.

  • If a ramp is valid, we expand the right pointer to find a wider ramp.
  • If a ramp is invalid, we fix by moving left to find a smaller starting candidate.
fun maxWidthRamp(nums: IntArray): Int {
    val n = nums.size
    val minBefore = IntArray(n)
    val maxAfter = IntArray(n)
    minBefore[0] = nums[0]
    for (i in 1 until n) {
        minBefore[i] = minOf(nums[i], minBefore[i - 1])
    }
    maxAfter[n - 1] = nums[n - 1]
    for (i in n - 2 downTo 0) {
        maxAfter[i] = maxOf(nums[i], maxAfter[i + 1])
    }

    var i = 0
    var j = 0
    var maxWidth = 0
    while (j < n) {
        if (minBefore[i] <= maxAfter[j]) {
            maxWidth = maxOf(maxWidth, j - i)
            j++
        } else {
            i++
        }
    }
    return maxWidth
}
  • Time Complexity: O(n) for pre-computing the prefix minimum and suffix maximum, and O(n) for two pointers scan, total O(n).
  • Space Complexity: O(n) for the prefix minimum and suffix maximum.