難度: Hard (?)
目前下列解法的時間複雜度: O(n)
題目說明
給定一數字都 >0 的整數陣列。
當你從另一個長度一樣,但數字都是 0 的另一個陣列開始,每次可以選一段區間每個數字都 +1 。
求最少幾次可以將另一個陣列變成給定的整數陣列。
解法
1. 先考慮 1 個山峰的形狀,直接取最高點。
2. 考慮 2 個山峰,先升高到中間低窪的部分,再分成 2 次分別升高 2 座山的部分。
3, 可以注意到 1 座山就是升高他左邊(或右邊,保持本座山都同向即可)最低窪處到山峰的高度差。
4. 所以,是"上升"(或下降,如果你取的是另外一邊),就在答案增加高度差。
source code