962. 最大寬度波

思路

假設現在陣列為 $[10,8,2,\dots12,9]$，對於 10 來說，他能跟後面的 12 配對。
因為寬度會縮減，後面能跟 12 配對的數字就不需要考慮了。
所以，固定右邊為 12 ，從前往後遍歷，一旦配對，就不用繼續下去了。
同樣的，假如現在固定左邊為 8，從後往前配對，一旦配到，也不用繼續下去了。
如此一來，可以寫出以下程式碼，會超時，原因在當沒有答案的時候，「不用繼續下去」帶來的速度加成會消失。

class Solution {
public:
    int maxWidthRamp(vector<int>& nums) {
        int n = nums.size();
        int res = 0;
        for(int i = 0; i < n; i++) {
            for(int j = n - 1; j >= max(res, i + 1); j--) {
                if(nums[i] <= nums[j]) {
                    res = max(res, j - i);
                    break;
                }
            }
        }
        return res;
    }
};

所以現在要找一個方法，既能做到上面說的事情，又不能用雙層循環。
在選擇開頭結尾的 $i,j$時，根據前面的觀察到的結論，
選擇開頭的候選項時，數值應該要從大選到小，
比如 $[9,8,1,0,1,9,4,0,4,1]$，開頭候選項就是 $[9,8,1,0]$。

1. 若是 9 能跟後面的 $x$配對，在 9 後面比它大的數字不需要考慮，因為它所能算出的寬度只會更少。
2. 後序參考項如果不能比 9 的答案好，就不需要列入參考
3. 因此，在 9 後面的參考項，只能比 9 小。
   接下來是結尾的配對項，為了讓寬度越寬越好，倒序遍歷。
   此時棧中元素單調遞減，跟棧頂元素配對，是最有機會成對的，拿固定的結尾不斷跟棧頂元素配對，
   就上面的例子，

• 拿 1 跟棧頂 0 配對，發現可以，將 0 彈出。
  • 在 1 前面，比 1 小的數字也能跟 0 配對，但是答案只會更差，所以可以彈出 0。
• 1 再跟棧頂元素 1 配對，發現依舊可以, 將 1 彈出。
• 1 再跟 8 比，發現不行，尾端數字更換成 4。
• …繼續拿 4 去比較，直到無法配對。

程式碼

單調棧

class Solution {
public:
    int maxWidthRamp(vector<int>& nums) {
        stack<int> stk;
        int n = nums.size();
        for(int i = 0; i < n; i++) { // 將單調遞減的數字加入棧中
            if(stk.empty() || nums[stk.top()] > nums[i]) {
                stk.push(i);
            }
        }
        int res = 0;
        for(int i = n - 1; i >= 0; i--) { // 倒序遍歷，如果當前數字比棧頂對應數字大，表示能形成坡
            while(!stk.empty() && nums[stk.top()] <= nums[i]) {
                res = max(res, i - stk.top());
                stk.pop();
            }
        }
        return res;
    }
};

複雜度分析

• 時間複雜度：$O(n)$
• 空間複雜度：$O(n)$