ETH官方钱包

前往
大廳
主題

LeetCode - 2970. Count the Number of Incremovable Subarrays I 解題心得

Not In My Back Yard | 2025-03-21 12:00:06 | 巴幣 2 | 人氣 20

題目連結:


題目意譯:
你被給定一個索引值從 0 開始數的正整數陣列 nums。

nums 中的一個子陣列是「移除後可遞增」的,代表著移除該子陣列後 nums 將變成嚴格遞增。例如說,子陣列 [3, 4] 是 [5, 3, 4, 6, 7] 的一個移除後可遞增子陣列,因為移除這個子陣列後會將 [5, 3, 4, 6, 7] 變成 [5, 6, 7],而其為嚴格遞增的。

回傳 nums 中移除後可遞增子陣列之數量。

注意到一個空陣列視為是嚴格遞增的。

一個子陣列為一個陣列中一段連續非空的元素序列。

限制:
1 ≦ nums.length ≦ 50
1 ≦ nums[i] ≦ 50



範例測資:
範例 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],而其不是嚴格遞增。


解題思維:
由於 nums 最長也只有 50,因此直接窮舉所有可能的子陣列並檢查剩餘元素是否嚴格遞增即可。時間複雜度為 O(n ^ 3),其中 n 為 nums 之長度。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。
追蹤 創作集

作者相關創作

更多創作