C++單調向量算法：得到山形數組的最少刪除次數

本題的其它解法

C++二分算法：得到山形數組的最少刪除次數

題目

我們定義 arr 是山形數組當且僅當它滿足：
arr.length >= 3
存在某個下標 i （從 0 開始）滿足 0 < i < arr.length - 1 且：
arr[0] < arr[1] < … < arr[i - 1] < arr[i]
arr[i] > arr[i + 1] > … > arr[arr.length - 1]
給你整數數組 nums? ，請你返回將 nums 變成山形狀數組的? 最少刪除次數。
示例 1：
輸入：nums = [1,3,1]
輸出：0
解釋：數組本身就是山形數組，所以我們不需要刪除任何元素。
示例 2：
輸入：nums = [2,1,1,5,6,2,3,1]
輸出：3
解釋：一種方法是將下標為 0，1 和 5 的元素刪除，剩余元素為 [1,5,6,3,1] ，是山形數組。
參數范圍：
3 <= nums.length <= 1000
1 <= nums[i] <= 109
題目保證 nums 刪除一些元素后一定能得到山形數組。

分析

本題可以轉換成：最長山形數組，再進一步轉換成最長升序子序列。

時間復雜度

時間復雜度O(nlogn)。分兩步：一，尋找左半部分。二，尋找右半部分。每步枚舉每個山頂，時間復雜度O(n)，每個山頂二分查找一次，時間復雜度O(logn)。

vLenToMin

vLenToMin[i]的含義是長度為i+1 的子序列的結尾，如果有多個符合的子序列，取結尾最小的。
比如：

原始數組	vLenToMin
1	1
1 2	{1}->{1,2}
2 1	{2}->{1}
1 2 3	{1}->{1,2
1 3 3 4 5	{1}->{1,3}->{1,3,4}->{1,3,4,5}
1 3 5 4	{1}->{1,3}->{1,3,5}->{1,3,4}

總結

一，只會在尾部增加元素。不會在其它位置增加元素。
二，不會刪除元素。
三，會替換元素。
四，嚴格遞增。
五，所有的數都小于當前值時，在末尾增加，顯然是升序。
六，it第一個大于等于n的迭代器，之前的元素一定嚴格小于it，而it<=n，故前面元素一定小于n。
后面的元素不會ij等于it，否則它就是*it。[ii,…)都大于等于n，所有ij不會小于n。
七，規則五和六保證了vLenToMin永遠嚴格遞增。

代碼

核心代碼

class Solution {
public:int minimumMountainRemovals(vector<int>& nums) {vector<int> vLeftLen,vRightLen;Do(vLeftLen, nums);Do(vRightLen, vector<int>(nums.rbegin(), nums.rend()));std::reverse(vRightLen.begin(), vRightLen.end());int iMaxLen = 0;for (int i = 1; i+1 < nums.size(); i++){if ((vLeftLen[i] > 1) && (vRightLen[i] > 1)){iMaxLen = max(iMaxLen, vLeftLen[i] + vRightLen[i] - 1);}}return nums.size() - iMaxLen;}void Do(vector<int>& vLen, const vector<int> nums){vector<int> vLenToMin;//vLenToMin[i]的含義是 長度為i+1 的子序列 的結尾，如果有多個符合的子序列，取結尾最小的。for (const auto& n : nums){auto it = std::lower_bound(vLenToMin.begin(), vLenToMin.end(), n);vLen.emplace_back(it - vLenToMin.begin() + 1);if (vLenToMin.end() == it){vLenToMin.emplace_back(n);}else{if (n < *it){*it = n;}}}}
};

測試用例

template
void Assert(const T& t1, const T& t2)
{
assert(t1 == t2);
}

template
void Assert(const vector& v1, const vector& v2)
{
if (v1.size() != v2.size())
{
assert(false);
return;
}
for (int i = 0; i < v1.size(); i++)
{
Assert(v1[i], v2[i]);
}
}

int main()
{
vector nums;
int res;
{
Solution slu;
nums = { 1,3,1 };
res = slu.minimumMountainRemovals(nums);
Assert(0, res);
}
{
Solution slu;
nums = { 2, 1, 1, 5, 6, 2, 3, 1 };
res = slu.minimumMountainRemovals(nums);
Assert(3, res);
}
{
Solution slu;
nums = { 9, 8, 1, 7, 6, 5, 4, 3, 2, 1 };
res = slu.minimumMountainRemovals(nums);
Assert(2, res);
}
{
Solution slu;
nums = { 100, 92, 89, 77, 74, 66, 64, 66, 64 };
res = slu.minimumMountainRemovals(nums);
Assert(6, res);
}
{
Solution slu;
nums = { 1, 2, 1, 3, 4, 4 };
res = slu.minimumMountainRemovals(nums);
Assert(3, res);
}

//CConsole::Out(res);

}

擴展閱讀

視頻課程

有效學習：明確的目標及時的反饋拉伸區（難度合適），可以先學簡單的課程，請移步CSDN學院，聽白銀講師（也就是鄙人）的講解。
https://edu.csdn.net/course/detail/38771

如何你想快

速形成戰斗了，為老板分憂，請學習C#入職培訓、C++入職培訓等課程
https://edu.csdn.net/lecturer/6176