前往
大廳
主題

LeetCode - 1413. Minimum Value to Get Positive Step by Step Sum 解題心得

Not In My Back Yard | 2022-05-03 00:00:01 | 巴幣 102 | 人氣 129

題目連結:


題目意譯:
給定一整數陣列 nums,且你開始於一個正整數值 startValue。

每次迭代中,你一步一步地計算出 startValue 漸漸加上 nums 中的元素之總和值(由左至右)。

回傳最小的 startValue 可能值,使得一步一步之總和永不小於 1。

限制:
1 ≦ nums.length ≦ 100
-100 ≦ nums[i] ≦ 100



範例測資:
範例 1:
輸入: nums = [-3,2,-3,4,2]
輸出: 5
解釋: 如果你選擇 startValue = 4,則在第三次迭代中你的一步一步之總和將小於 1。
一步一步總和
startValue = 4 | startValue = 5 | nums
  (4 -3 ) = 1  | (5 -3 ) = 2    |  -3
  (1 +2 ) = 3  | (2 +2 ) = 4    |  2
  (3 -3 ) = 0  | (4 -3 ) = 1    |  -3
  (0 +4 ) = 4  | (1 +4 ) = 5    |  4
  (4 +2 ) = 6  | (5 +2 ) = 7    |  2

範例 2:
輸入: nums = [1,2]
輸出: 1
解釋: 最小初始值應為正。

範例 3:
輸入: nums = [1,-2,-3]
輸出: 5


解題思維:
一步一步地加總 nums 中的元素,取其中總和值最小的出來,設其值為 M。

可以看到由於 M 是其中最小的總和值,因此如果 M > 0,則 startValue 最小即為 1(因為不管怎樣加都不會小於 1);反之,如果 M ≦ 0,例如說 M = -5,則 startValue 應至少為 6。因此可以看到此時的 startValue 最小值即為 1 - M。




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

創作回應

更多創作