Минимална стойност за получаване на положителна стъпка по стъпка Решение за Leetcode


Ниво на трудност Лесно
Често задавани в Swiggy
Array

Декларация за проблема

В този проблем ни се дава поредица от числа (може да бъде положително отрицателно или нула). Трябва да вземем положително цяло число със себе си и след това ще започнем да добавяме всички цели числа от това масив отляво надясно с него.
Искаме минималното положително цяло число, което трябва да вземем в началото, така че по всяко време текущата ни сума винаги да остане положителна.

Пример

nums = [-3,2,-3,4,2]
5

Обяснение:

Минимална стойност за получаване на положителна стъпка по стъпка Решение за Leetcode
Тук можем да видим, че ако изберем startValue = 5, ще получим всички междинни суми положителни. Можем да проверим и за startValue = 4, което не е правилното решение.

nums = [1,2]
1

Обяснение:

Минималната начална стойност трябва да бъде положителна.

Подход

Да предположим, че имаме масив, nums = [-3,2, -3,4,2]
Сега, ако изберем първоначалната стойност като 2 и продължим да добавяме елементи отляво надясно, тогава:

Минимална стойност за получаване на положителна стъпка по стъпка Решение за Leetcode

В горния пример избрахме първоначалната стойност като 2. Нашата сума няма да остане положителна всеки път, така че се нуждаем от по-голям елемент.

Нека първоначалната вал е 5.
Минимална стойност за получаване на положителна стъпка по стъпка Решение за Leetcode
Сега можем ясно да видим, че ако началната стойност е 5, тогава със сигурност можем да пътуваме из масива, запазвайки текущата си сума винаги положителна. 5 може да бъде отговорът, ако това е най-малкото цяло число.
Нека помислим за ситуация, ако изберем val = 0 с нас в началото.

Минимална стойност за получаване на положителна стъпка по стъпка Решение за Leetcode

Сега, можем ли да кажем, че ако преодолеем стойността на най-отрицателната текуща сума (-4 в текущия пример), тогава можем безпроблемно да предадем масива.
Както в горния пример, най-отрицателната стойност е -4, за да я преодолеем, трябва да я направим 1 (защото е необходимо най-малкото положително цяло число).

Така че искаме стойност 1 - (- 4) = 5 да премине най-негативната ситуация.
също така видяхме, че 5 може да премине решението.

И ако няма отрицателна текуща сума, просто ще изведем 1, защото искаме положително интегрално решение.

И така, нашият алгоритъм ще бъде:

1. Трябва да търсим най-отрицателното решение, така че ще прекосим целия масив.
2. Във всяка итерация на контур ние ще проверим дали текущата сума е минимална или не и ще актуализираме съответно нашата минимална стойност.
3. Накрая, за да направим тази най-отрицателна стойност на 1, просто ще я извадим от 1. (напр. Ако min = -4, val = 1 - (- 4) = 5).

изпълнение

Програма C ++ за минимална стойност за получаване на положително решение стъпка по стъпка Решение Leetcode

#include <iostream>
#include<vector>
using namespace std;

int minStartValue(vector<int>& nums) {
    
    int min=0,sum=0;
    for (int i = 0; i < nums.size(); i++){
        sum+=nums[i];
        min=min<sum?min:sum;
    }
    
    return 1-min;
}

int main() {
    vector<int> nums{-3,2,-3,4,2}; 
    cout<<minStartValue(nums)<<endl;	
  return 0;
}
5

Програма Java за минимална стойност за получаване на положително решение стъпка по стъпка Решение на Leetcode

import java.util.*;

class Rextester{
    
    public static int minStartValue(int[] nums) 
    {
        Integer min=0,sum=0;
        for(int i:nums){
            sum+=i;
            min=Math.min(min,sum);
        }
        return 1-min;
    }
    
    public static void main(String args[])
    {
       	int[]nums={-3,2,-3,4,2};
        int ans=minStartValue(nums);
        System.out.println(ans);
    }
}
5

Анализ на сложността за минимална стойност за получаване на положително решение стъпка по стъпка Решение на Leetcode

Сложност във времето

На): Защото ние обхождаме дадения масив линейно, като по този начин сложността ни във времето ще бъде O (n).

Сложност на пространството 

O (1): Не сме използвали допълнително пространство, поради което сложността ни в пространството ще бъде постоянна.