主題
題目: 1671. Minimum Number of Removals to Make Mountain Array
難度: Hard
目前下列解法的時間複雜度: O(n*lg(n))
題目說明
給你長度n的一條數字陣列，問要讓這條陣列變成山形，最少需要刪掉幾個數字。
* 山形: 先是嚴格遞增序列到某處(長度>=2)，然後在某處開始變成嚴格遞減序列(長度>=2)。
解法
先解基本的LIS: 300. Longest Increasing Subsequence
最基本的LIS想法是: 每次往前看，若某個數字比我小，則看看他那一格的LIS答案有沒有比較大，若有則更新。
本來是 "數字->長度" ，但不仿換個方向: "長度->數字" 再轉一下變成 "長度->最小數字" 。
長度是0,1,2,3, ... ，所以可以變成 "索引值->最小數字" 。
從原本的 "數字->長度" 中，因為要從數字比較小的當中找LIS答案最大的再+1，若相同LIS答案的數字只留下最小的，則: 數字較大者長度也較大 => "長度->最小數字" 的陣列是遞增序列。
於是每當檢驗新的數字時，二分搜該數字會落在那裡，該位置索引值即 "子序列最後的數字是該數字時的LIS答案" ，若是落在最後則直接新增該數字到 "長度->最小數字" 的最後。
於是再回來看這題
對於每個不是最邊邊的數字假設其為山峰，然後對左右側分別算LIS,LD(decreasing)S的答案，拿n減掉那兩個再+1補回山峰就是這次假設的答案。每個假設都做完後回傳最小的那個即可。
注意到LIS再每看完一個數字後就有"在此之前的數字組成的陣列的LIS答案"，所以可以先對每個 i 做 0~i 的 LIS 並記錄下來， LDS 同理。共費時 O(n*lg(n)) 。
於是在假設山峰的時候只要 n * O(1) = O(n) 即可。
source code
當然你要用 fake segment tree 解也是可以啦，也是 O(n*lg(n)) ，只是係數很高。像這樣。
難度: Hard
目前下列解法的時間複雜度: O(n*lg(n))
題目說明
給你長度n的一條數字陣列，問要讓這條陣列變成山形，最少需要刪掉幾個數字。
* 山形: 先是嚴格遞增序列到某處(長度>=2)，然後在某處開始變成嚴格遞減序列(長度>=2)。
解法
先解基本的LIS: 300. Longest Increasing Subsequence
最基本的LIS想法是: 每次往前看，若某個數字比我小，則看看他那一格的LIS答案有沒有比較大，若有則更新。
本來是 "數字->長度" ，但不仿換個方向: "長度->數字" 再轉一下變成 "長度->最小數字" 。
長度是0,1,2,3, ... ，所以可以變成 "索引值->最小數字" 。
從原本的 "數字->長度" 中，因為要從數字比較小的當中找LIS答案最大的再+1，若相同LIS答案的數字只留下最小的，則: 數字較大者長度也較大 => "長度->最小數字" 的陣列是遞增序列。
於是每當檢驗新的數字時，二分搜該數字會落在那裡，該位置索引值即 "子序列最後的數字是該數字時的LIS答案" ，若是落在最後則直接新增該數字到 "長度->最小數字" 的最後。
於是再回來看這題
對於每個不是最邊邊的數字假設其為山峰，然後對左右側分別算LIS,LD(decreasing)S的答案，拿n減掉那兩個再+1補回山峰就是這次假設的答案。每個假設都做完後回傳最小的那個即可。
注意到LIS再每看完一個數字後就有"在此之前的數字組成的陣列的LIS答案"，所以可以先對每個 i 做 0~i 的 LIS 並記錄下來， LDS 同理。共費時 O(n*lg(n)) 。
於是在假設山峰的時候只要 n * O(1) = O(n) 即可。
source code
