昨天京東招聘服務號發文稱：京東TGT-頂尖青年技術天才計劃全球啟動，主要面向的是全球高校本碩博在校生，應屆生以及畢業兩年的技術人才，旨在與全球技術天才一起探索技術前沿，并且薪酬不設上限。誠意滿滿，如果覺得自己是技術天才的可以去投遞簡歷了。

看到這個消息我是又激動又失望，激動是因為企業對人才的渴望和重視，失望是因為面向的是應屆生和畢業兩年的技術天才。所以要想找到好的工作，在畢業之前一定要抓住機會。如果錯失機會，即便是技術天才，畢業兩年之后也不符合招聘要求。

--------------下面是今天的算法題--------------

來看下今天的算法題，這題是LeetCode的第1526題：形成目標數組的子數組最少增加次數，難度是困難。

給你一個整數數組 target 和一個數組 initial ，initial 數組與 target 數組有同樣的維度，且一開始全部為 0 。請你返回從 initial 得到 target 的最少操作次數，每次操作需遵循以下規則：

在 initial 中選擇任意子數組，并將子數組中每個元素增加 1 。答案保證在 32 位有符號整數以內。

示例1：

輸入：target = [1,2,3,2,1] 輸出：3 解釋：我們需要至少 3 次操作從 intial 數組得到 target 數組。 [0,0,0,0,0] 將下標為 0 到 4 的元素（包含二者）加 1 。 [1,1,1,1,1] 將下標為 1 到 3 的元素（包含二者）加 1 。 [1,2,2,2,1] 將下表為 2 的元素增加 1 。 [1,2,3,2,1] 得到了目標數組。

示例2：

輸入：target = [3,1,5,4,2] 輸出：7 解釋：(initial)[0,0,0,0,0] -> [1,1,1,1,1] -> [2,1,1,1,1] -> [3,1,1,1,1] -> [3,1,2,2,2] -> [3,1,3,3,2] -> [3,1,4,4,2] -> [3,1,5,4,2](target)。

• 1 <= target.length <= 10^5

• 1 <= target[i] <= 10^5

問題分析

這題說的是把一個值全為 0 的數組轉化為target數組，所需要的最少操作次數。每次操作我們可以選擇任意子數組，然后對這個子數組中的所有元素加 1 。

數組中元素的大小我們可以把它看作是山的高度，如果山只有一個山峰，比如數組左邊元素是遞增的，右邊元素是遞減的，那么最少操作次數就是山峰減山底的值，如示例一中就是這種情況，結果就是 3-0，結果為 3 。

很明顯這座山可能會有多個山峰，如示例二中，有 3 ，5 兩個山峰，第一個山峰需要操作的次數是 3-0 ，結果是 3 ，第二個山峰需要操作的次數是 5-1 ，結果是 4 ，所以總的操作次數是 7 。

所以這題就比較簡單了，我們只需要累加所有山峰到山底的差值即可，代碼如下。

JAVA：

public int minNumberOperations(int[] target) {     int ans = 0;     int i = 0, n = target.length;     int preMin = 0;// 起始點的波谷在位置 0 。     while (i < n) {         while (i + 1 < n && target[i] <= target[i + 1])// 上升             i++;         int start = target[i];// 波峰         while (i + 1 < n && target[i] >= target[i + 1])// 下降             i++;         ans += start - preMin;// 累加波峰減波谷         preMin = target[i++];// 更新波谷     }     return ans; }

C++：

public:     int minNumberOperations(vector
               
 &target) {         int ans = 0;         int i = 0, n = target.size();         int preMin = 0;// 起始點的波谷在位置 0 。         while (i < n) {             while (i + 1 < n && target[i] <= target[i + 1])// 上升                 i++;             int start = target[i];// 波峰             while (i + 1 < n && target[i] >= target[i + 1])// 下降                 i++;             ans += start - preMin;// 累加波峰減波谷             preMin = target[i++];// 更新波谷         }         return ans;     }
       

上面代碼中我們需要先找到山峰，然后才能計算，實際不需要直接查找，我們用數組中后面的值減去前面的值，如果為正的，說明朝著山峰的方向走，直接累加，如果是負的，說明朝著山底的方向走，直接忽略，這樣代碼會更加簡潔。

JAVA：

public int minNumberOperations(int[] target) {     int ans = target[0];     for (int i = 1, n = target.length; i < n; i++)         ans += Math.max(0, target[i] - target[i - 1]);     return ans; }

C++：

public:     int minNumberOperations(vector
               
 &target) {         int ans = target[0];         for (int i = 1, n = target.size(); i < n; i++)             ans += max(0, target[i] - target[i - 1]);         return ans;     }
       

筆者簡介

博哥，真名：王一博，畢業十多年， 作者，專注于 數據結構和算法 的講解，在全球30多個算法網站中累計做題2000多道，在公眾號中寫算法題解800多題，對算法題有自己獨特的解題思路和解題技巧，喜歡的可以給個關注 。也可以獲取的整理的1000多頁的PDF算法題。