Number.MAX_SAFE_INTEGER
Number.MIN_SAFE_INTEGER
PHP_INT_MAX
PHP_INT_MIN
int(^uint(0) >> 1) # 首位 0,其余位 1
^int(^uint(0) >> 1) # 首位 1,其余位 0
sys.maxint # python 2
-sys.maxint - 1 # python 2
sys.maxsize # python 3
-sys.maxsize - 1 # python 3
float('inf') # 正无穷大,通用
float('-inf') # 负无穷大,通用
Integer.MIN_VALUE
Integer.MAX_VALUE
int.MaxValue
int.MinValue
INT_MAX
INT_MIN
INT_MAX
INT_MIN
给你一个整数数组 nums 。你可以选定任意的 正数 startValue 作为初始值。
你需要从左到右遍历 nums 数组,并将 startValue 依次累加上 nums 数组中的值。
请你在确保累加和始终大于等于 1 的前提下,选出一个最小的 正数 作为 startValue 。
示例 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
var minStartValue = function(nums) {
const n = nums.length
let minValue = Number.MAX_SAFE_INTEGER, total = 0
for (let i = 0; i < n; i++) {
total += nums[i]
if (total < minValue) minValue = total
}
return minValue >= 0 ? 1 : -minValue + 1
};
function minStartValue(nums: number[]): number {
const n = nums.length
let minValue = Number.MAX_SAFE_INTEGER, total = 0
for (let i = 0; i < n; i++) {
total += nums[i]
if (total < minValue) minValue = total
}
return minValue >= 0 ? 1 : -minValue + 1
};
class Solution {
function minStartValue($nums) {
$total = 0;
$minValue = PHP_INT_MAX;
foreach($nums as $num) {
$total += $num;
if ($total < $minValue) $minValue = $total;
}
return $minValue >= 0 ? 1 : -$minValue + 1;
}
}
func minStartValue(nums []int) int {
total, minValue := 0, int(^uint(0) >> 1)
for _, num := range nums {
total += num
if total < minValue {
minValue = total
}
}
if minValue >= 0 {
return 1
}
return -minValue + 1
}
class Solution:
def minStartValue(self, nums: List[int]) -> int:
minValue, total = sys.maxsize, 0
for _, num in enumerate(nums):
total += num
if minValue > total: minValue = total
return -minValue + 1 if minValue < 0 else 1
class Solution {
public int minStartValue(int[] nums) {
int minValue = Integer.MAX_VALUE, total = 0;
for (int num : nums) {
total += num;
if (total < minValue) minValue = total;
}
return minValue >= 0 ? 1 : -minValue + 1;
}
}
public class Solution {
public int MinStartValue(int[] nums) {
int minValue = int.MaxValue, total = 0;
foreach (int num in nums) {
total += num;
if (total < minValue) minValue = total;
}
return minValue >= 0 ? 1 : -minValue + 1;
}
}
int minStartValue(int* nums, int numsSize){
int total = 0, minValue = INT_MAX;
for (int i = 0; i < numsSize; i++) {
total += nums[i];
if (total < minValue) minValue = total;
}
return minValue >= 0 ? 1 : -minValue + 1;
}
public:
int minStartValue(vector<int>& nums) {
int total = 0, minValue = INT_MAX;
for (int num : nums) {
total += num;
if (total < minValue) minValue = total;
}
return minValue >= 0 ? 1 : -minValue + 1;
}
};
从最小值(最小数)到最大值(最小数乘以长度 + 1)查找第一个让数组和大于 0 的数:upper_bound
var minStartValue = function(nums) {
const n = nums.length, minNum = _.min(nums)
if (minNum >= 0) return 1
let l = 1, r = -minNum * n + 1
while (l <= r) {
const m = Math.floor((l + r) / 2)
if (gt0(nums, m)) r = m - 1
else l = m + 1
}
return l
};
const gt0 = (nums, startValue) => {
for (const num of nums) {
startValue += num
if (startValue <= 0) return false
}
return true
}
function minStartValue(nums: number[]): number {
const minNum = nums.reduce((minValue, cur) => Math.min(minValue, cur), Number.MAX_SAFE_INTEGER)
if (minNum >= 0) return 1
const n = nums.length
let l = 1, r = -minNum * n + 1
while (l <= r) {
const m = l + r >> 1
if (gt0(nums, m)) r = m - 1
else l = m + 1
}
return l
};
function gt0(nums: number[], startValue: number): boolean {
for (const num of nums) {
startValue += num
if (startValue <= 0) return false
}
return true
}
class Solution {
function minStartValue($nums) {
$min = min($nums);
if ($min >= 0) return 1;
$n = count($nums);
$l = 1;
$r = -$min * $n + 1;
while ($l <= $r) {
$m = $l + $r >> 1;
if ($this->gt0($nums, $m)) $r = $m - 1;
else $l = $m + 1;
}
return $l;
}
function gt0($nums, $startValue) {
foreach ($nums as $num) {
$startValue += $num;
if ($startValue <= 0) return false;
}
return true;
}
}
func minStartValue(nums []int) int {
minValue := int(^uint(0) >> 1)
for _, num := range nums {
if minValue > num {
minValue = num
}
}
if minValue >= 0 {
return 1
}
l, r := 1, -minValue * len(nums) + 1
for l <= r { // 自己实现
m := (l + r) >> 1
if gt0(nums, m) {
r = m - 1
} else {
l = m + 1
}
}
return l
}
func gt0(nums []int, startValue int) bool {
for _, num := range nums {
startValue += num
if startValue <= 0 {
return false
}
}
return true
}
func minStartValue(nums []int) int {
minNum := int(^uint(0) >> 1)
for _, num := range nums {
if minNum > num {
minNum = num
}
}
if minNum >= 0 {
return 1
}
return max(1, sort.Search(-minNum * len(nums) + 1, func(startValue int) bool { // 调用 sort.Search
return gt0(nums, startValue)
}))
}
func gt0(nums []int, startValue int) bool {
for _, num := range nums {
startValue += num
if startValue <= 0 {
return false
}
}
return true
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
class Solution {
public int minStartValue(int[] nums) {
int minNum = Arrays.stream(nums).min().getAsInt();
if (minNum >= 0) return 1;
int l = 1, r = -minNum * nums.length + 1;
while (l <= r) {
int m = l + r >> 1;
if (gt0(nums, m)) r = m - 1;
else l = m + 1;
}
return l;
}
public boolean gt0(int[] nums, int startValue) {
for (int num : nums) {
startValue += num;
if (startValue <= 0) return false;
}
return true;
}
}
public class Solution {
public int MinStartValue(int[] nums) {
int minNum = nums.Min();
if (minNum >= 0) return 1;
int l = 1, r = -minNum * nums.Length + 1;
while (l <= r) {
int m = l + r >> 1;
if (gt0(nums, m)) r = m - 1;
else l = m + 1;
}
return l;
}
private bool gt0(int[] nums, int startValue) {
foreach (int num in nums) {
startValue += num;
if (startValue <= 0) return false;
}
return true;
}
}
#define MIN(a, b) a < b ? a : b
static bool gt0(int* nums, int startValue, int numsSize) {
for (int i = 0; i < numsSize; i++) {
startValue += nums[i];
if (startValue <= 0) return false;
}
return true;
}
int minStartValue(int* nums, int numsSize){
int minNum = INT_MAX;
for (int i = 0; i < numsSize; i++) {
minNum = MIN(minNum, nums[i]);
}
if (minNum >= 0) return 1;
int l = 1, r = -minNum * numsSize + 1;
while (l <= r) {
int m = l + r >> 1;
if (gt0(nums, m, numsSize)) r = m - 1;
else l = m + 1;
}
return l;
}
class Solution {
private:
int gt0(vector<int>& nums, int startValue) {
for (int num: nums) {
startValue += num;
if (startValue <= 0) return false;
}
return true;
}
public:
int minStartValue(vector<int>& nums) {
int minNum = *min_element(nums.begin(), nums.end());
if (minNum >= 0) return 1;
int l = 1, r = -minNum * nums.size() + 1;
while (l <= r) {
int m = l + r >> 1;
if (gt0(nums, m)) r = m - 1;
else l = m + 1;
}
return l;
}
};
class Solution:
def minStartValue(self, nums: List[int]) -> int:
minNum = min(nums)
if minNum >= 0: return 1
l, r = 1, -minNum * len(nums) + 1
while l <= r:
m = l + r >> 1
if self.gt0(nums, m): r = m - 1
else: l = m + 1
return l
def gt0(self, nums: List[int], startValue: int) -> bool:
for num in nums:
startValue += num
if startValue <= 0: return False
return True