ETH官方钱包

前往
大廳
主題

[leetcode]1526. Minimum Number of Increments on Subarrays to Form a Target Array

???\~O_O~/??? | 2021-08-23 12:00:01 | 巴幣 2 | 人氣 317

題目: 1526. Minimum Number of Increments on Subarrays to Form a Target Array
難度: Hard (?)
目前下列解法的時間複雜度: O(n)


題目說明

給定一數字都 >0 的整數陣列。
當你從另一個長度一樣,但數字都是 0 的另一個陣列開始,每次可以選一段區間每個數字都 +1 。
求最少幾次可以將另一個陣列變成給定的整數陣列。


解法

1. 先考慮 1 個山峰的形狀,直接取最高點。
2. 考慮 2 個山峰,先升高到中間低窪的部分,再分成 2 次分別升高 2 座山的部分。
3, 可以注意到 1 座山就是升高他左邊(或右邊,保持本座山都同向即可)最低窪處到山峰的高度差。
4. 所以,是"上升"(或下降,如果你取的是另外一邊),就在答案增加高度差。


source code

創作回應

相關創作

更多創作