단계적으로 긍정적 인 단계를 얻기위한 최소값 합계 Leetcode 솔루션

난이도 쉽게
자주 묻는 질문 Swiggy
알고리즘 배열 코딩 인터뷰 인터뷰 준비 리트코드 LeetCodeSolutions조회수 45

문제 정책

이 문제에서는 일련의 숫자가 주어집니다 (양수 또는 XNUMX 일 수 있음). 우리는 양의 정수를 가져와야합니다. 그리고이 모든 정수를 더하기 시작할 것입니다. 정렬 왼쪽에서 오른쪽으로.
우리는 처음에 가져와야 할 최소 양의 정수를 원하므로 언제든지 현재 합계가 항상 양수로 유지됩니다.

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 ++ 프로그램을 통해 단계적으로 긍정적 인 단계를 얻을 수 있습니다.

#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 프로그램 Sum 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

단계적 합리 코드 솔루션을 통해 긍정적 인 단계를 얻기위한 최소값에 대한 복잡성 분석

시간 복잡성

의 위에): 왜냐하면 우리는 주어진 배열을 선형으로 순회하고 있기 때문에 우리의 시간 복잡도는 O (n)이 될 것입니다.

공간 복잡성 

O (1) : 추가 공간을 사용하지 않았으므로 공간 복잡성은 일정합니다.

코멘트를 남겨

Translate »
1