主題
題目連結：
題目意譯：
你被給定一個索引值從 0 開始數的正整數陣列 nums。
nums 中的一個子陣列是「移除後可遞增」的，代表著移除該子陣列後 nums 將變成嚴格遞增。例如說，子陣列 [3, 4] 是 [5, 3, 4, 6, 7] 的一個移除後可遞增子陣列，因為移除這個子陣列後會將 [5, 3, 4, 6, 7] 變成 [5, 6, 7]，而其為嚴格遞增的。
回傳 nums 中移除後可遞增子陣列之數量。
注意到一個空陣列視為是嚴格遞增的。
一個子陣列為一個陣列中一段連續非空的元素序列。
限制：
1 ≦ nums.length ≦ 10 ^ 5
1 ≦ nums[i] ≦ 10 ^ 9
範例測資：
範例 1：
輸入： nums = [1,2,3,4]
輸出： 10
解釋： 10 個移除後可遞增子陣列為：[1] 、 [2] 、 [3] 、 [4] 、 [1,2] 、 [2,3] 、 [3,4] 、 [1,2,3] 、 [2,3,4] 和 [1,2,3,4]，因為移除這些子陣列中的其中任意一個便會使 nums 變成嚴格遞增。注意到你不得選擇一個空陣列來移除。
範例 2：
輸入： nums = [6,5,7,8]
輸出： 7
解釋： 7 個移除後可遞增子陣列為：[5] 、 [6] 、 [5,7] 、 [6,5] 、 [5,7,8] 、 [6,5,7] 和 [6,5,7,8]。
可以證明 nums 中只有 7 個移除後可遞增子陣列。
範例 3：
輸入： nums = [8,7,6,6]
輸出： 3
解釋： 3 個移除後可遞增子陣列為：[8,7,6] 、 [7,6,6] 和 [8,7,6,6]。注意到 [8,7] 不是一個移除後可遞增子陣列，因為移除 [8,7] 後 nums 變成了 [6,6]，而其不是嚴格遞增。
解題思維：
（令 n = nums.length）
可以看到這些子陣列可以將 nums 分成三個部份——即該子陣列「本身」以及其左右剩餘元素形成的子陣列（可能為空）。
現在假設對於「左邊」的某個子陣列 nums[0] ~ nums[i] 滿足 nums[0] < nums[1] < …… < nums[i] 且已知「右邊」的子陣列可以往左延伸到何處，也就是說已知最小的索引值 j 滿足 i + 1 < j（注意到移除後可遞增子陣列不得為空）且 nums[i] < nums[j] < nums[j + 1] < …… < nums[n - 1]（注意到當 j == n 時，右邊的子陣列為空，此時視為符合條件）。
則此時「中間」即是一個移除後可遞增子陣列，並且該子陣列可以一直往右延伸漸漸地把右邊吃掉並維持移除後可遞增的特性。因此以 nums[0] ~ nums[i] 左邊的子陣列的情況下，移除後可遞增子陣列的數量為 n - j。
此時如果把 nums[i + 1] 改加到左邊的話，會有兩種情況：
一種是 nums[i] ≧ nums[i + 1]，此時可以看到不可能會有左邊包含 nums[i + 1]（不符合嚴格遞增），因此加入 nums[i + 2] 、 nums[i + 3] 等都沒有用；
而如果 nums[i] < nums[i + 1]，則我們可以為 nums[0] ~ nums[i + 1] 這個子陣列找到其對應的 j 值來計算有多少移除後可遞增子陣列以它作為左邊。並且 nums[0] ~ nums[i + 1] 的 j 值必定不會小於 nums[0] ~ nums[i] 時的 j 值，因此我們可以「繼承」後者的 j 值來往右檢查。
而上述情況在 nums[i + 1] 轉換到 nums[i + 2] 也會發生，nums[i + 2] 到 nums[i + 3] 也是，以此類推。
而最一開始我們可以從左邊為空的情況開始，此時的 j 值不需要判斷 nums[i] < nums[j]（即 nums[j] 要大過左邊最後一個元素）的這種條件，只要一直從 nums[n - 1] 往左延伸直到不符合 0 < j（一樣，記得要移除的子陣列不得為空）且 nums[j] < nums[j + 1] < …… < nums[n - 1] 為止。
剩下就可以根據上面的方式推得 nums[0] 作為左邊、nums[0] ~ nums[1] 作為左邊等情況的移除後可遞增子陣列之數量。全數加總便可得到所求。
可以看到「i」和「j」都只會一直往右而變大（「j」只有在最一開始往左，後面的步驟只會往右或不變），不會變小。而對於一種「左邊」來說計算移除後可遞增子陣列之數量即是計算 n - j 之值。因此總體時間複雜度為 O(n)。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
