難度: Medium
類型: Array, Queue,Sliding Window, Heap (Priority Queue), Ordered Set, Monotonic Queue
CPP程式下載: 2762_1.cpp 2762_2.cpp
前情題要:
連續的子陣列。任意個子陣列裡的值相減必須小於等於2
思考方式:
1. 用 Sliding Window 的方式, 抓 high low index。
2. 解出來不難, 但要夠快, 能排名在前面不容易。
3. 2762_1.cpp, 用 multiset, 能自動排序且數值可以重複, 最右邊的最大值減掉最左邊的最小值, 就能判斷是否符合 substring 要相減 "<=2" 的條件。每次sliding window 的左邊 low index 移動前, 要先找到multiset中相同值並移除。這可以做到 230~240 ms 的速度, 約Beat 22~23%, 而且multiset存了太多數值, 空間約156MB, Beat 19%。
4. 2762_2.cpp, 相減要小於等於2, 所以取任一值當中心點, 其他的數字只可能在 -2~+2 的範圍, 所以只需要存五個值的出現次數 "freq_range[5]"。當移動sliding window 的左邊 low index 時, 根據 low index 位置數值和前次的 low index 數值的差, 來移動freq_range[5]; freq_range[2]永遠都是目前 low index那個值出現的次數。一直保留前次的high index, 並讓sliding window試著往右邊推進。因為只有存五個值的freq, 所以移動起來容易(運算少), 而且不須存大量的資料。在時間和空間上都有效率。不過就是程式比較繁瑣, 要考慮的 boundary condition 比較多。
複雜度思考:
Time Complexity: O( 2*N )
Space Complexity: O( 16*sizeof(int) + sizeof(long long) )
結果:
Runtime: 78 ms, Beats: 91.90%
Memory: 111.69 MB, Beats: 97.92%
