주식 스팬 문제


난이도 중급
자주 묻는 질문 아마존 배달 MAQ
스택

이 문제는“주식 스팬 문제”는 재정적 측면에서 발생합니다. 이 문제에서 우리는 매일의 주가에 대한 주식 스팬을 찾습니다. 전날의 주식 가격이 주식의 가격보다 작거나 같은 특정 일 직전의 최대 연속 일수를 스팬이라고합니다.

주식 스팬 문제

위의 재고 스팬 문제 이미지에서와 같이 –

1 일째, 주가 100 – 연속 된 전일의 더 작은 주가가 없으므로 범위 = 1

2 일, 주가 80 – 연속 된 전일의 주가가 더 작지 않으므로 범위 = 1

3 일, 주가 60 – 연속 된 전일의 주가가 더 작지 않으므로 범위 = 1

4 일차, 주가 70 – 3 일차의 주가가 더 작습니다. 즉, 60 일, 스팬 = 2

5 일, 주가 60 – 연속 된 전일의 주가가 더 작지 않으므로 범위 = 1

6 일, 주가 75 – 3 일, 4 일, 5 일은 주가가 더 작습니다 (예 : 각각 60, 70, 60), 따라서 범위 = 4

7 일차 주가 85 – 2 일차, 3 일차, 4 일차, 5 일차 및 6 일차는 주가가 더 작습니다 (예 : 각각 80, 60, 70, 60, 75), 따라서 범위 = 6

입출력에 대한 이해를 위해 주식 스팬 문제의 몇 가지 예를 살펴 보겠습니다.

입력 : 가격 = {100, 80, 60, 70, 60, 75, 85}

출력 : 7 일 기간 : 1 1

입력 : 가격 = {10, 4, 5, 90, 120, 80}

출력 : 6 일의 기간 : 1 1 2 4

스택을 사용하지 않고

주식 스팬 문제에 대한 순진한 방법

암호알고리즘

  1. 초기화 정렬 n 일의 주가를 저장합니다.
  2. 범위를 저장하기 위해 크기가 n 인 또 다른 배열 S를 만듭니다.
  3. 1에서 n-1로 이동하고 S []의 현재 인덱스에있는 값을 1로 설정합니다. 외부 루프의 인덱스에있는 가격이 현재의 가격보다 크거나 같은 동안 외부 루프 -1에서 0까지 내부 루프를 초기화합니다. 내부 루프의 인덱스를 사용하고 내부 루프의 모든 단계에서 S []의 현재 인덱스를 증가시킵니다.
  4. 배열 S []를 인쇄합니다.

주식 스팬 문제에 대한 C ++ 프로그램

#include <bits/stdc++.h> 
using namespace std;  
  
void calculateSpan(int price[], int n, int S[]){  
    S[0] = 1;  
  
    for(int i = 1; i < n; i++){  
        S[i] = 1; 
  
        for (int j = i - 1; (j >= 0) &&  
                (price[i] >= price[j]); j--)  
            S[i]++;  
    }  
}  
  
void display(int arr[], int n){
    cout<<"Span of "<<n<<" days : "; 
    for (int i = 0; i < n; i++)  
        cout << arr[i] << " ";  
}  
  
int main(){  
    
    int price[] = {100, 80, 60, 70, 60, 75, 85};  
    int n = sizeof(price) / sizeof(price[0]);  
    int S[n];  
  
    calculateSpan(price, n, S);  
  
    display(S, n);  
  
    return 0;  
}
Span of 7 days : 1 1 1 2 1 4 6

주식 스팬 문제를위한 자바 프로그램

Span of 7 days : 1 1 1 2 1 4 6

복잡성 분석

시간 복잡성 : O (n * n) 여기서 n은 주가가 제공되는 일수입니다.

보조 공간 : O (n) n 주가에 대해 스팬을 저장하기 위해 공간을 사용했기 때문입니다.

스택 사용

재고 스팬 문제를위한 효율적인 방법

암호알고리즘

  1. n 일의 주가를 저장하도록 배열을 초기화합니다.
  2. 스팬과 정수 유형의 스택 st를 저장하기 위해 크기가 n 인 또 다른 배열 S를 만듭니다.
  3. 1에서 n-1로 이동하는 동안 스택 비어 있지 않고 현재 인덱스의 가격이 스택 상단의 값과 동일한 인덱스의 가격보다 크거나 같으면 상단을 팝합니다.
  4. 현재 인덱스 + 1이 스택이면 S []의 현재 인덱스를 업데이트하고, 그렇지 않으면 현재 인덱스는 스택의 맨 위에 있고 스택에 현재 인덱스를 푸시 / 삽입합니다.
  5. 루프 후에 배열 S []를 인쇄합니다.

주식 스팬 문제에 대한 C ++ 프로그램

#include <bits/stdc++.h> 
using namespace std;  
  
void calSpan(int price[], int n, int S[]){  
    
    stack<int> st; 
    st.push(0); 
  
    S[0] = 1; 
  
    for(int i = 1; i < n; i++){ 
        while ((!st.empty()) && (price[st.top()] <= price[i])){ 
            st.pop(); 
        }
  
        S[i] = (st.empty()) ? (i + 1) : (i - st.top()); 
  
        st.push(i); 
    }   
}  
  
void display(int arr[], int n){
    cout<<"Span of "<<n<<" days : "; 
    for (int i = 0; i < n; i++)  
        cout << arr[i] << " ";  
}  
  
int main(){  
    
    int price[] = {100, 80, 60, 70, 60, 75, 80 };  
    int n = sizeof(price) / sizeof(price[0]);  
    int S[n];  
  
    calSpan(price, n, S);  
  
    display(S, n);  
  
    return 0;  
}
Span of 7 days : 1 1 1 2 1 4 6

주식 스팬 문제를위한 자바 프로그램

import java.util.Arrays; 
import java.util.Stack; 
  
class spanStock{ 
    
    static void calSpan(int price[], int n, int S[]){ 
        
        Stack<Integer> st = new Stack<>(); 
        st.push(0); 
  
        S[0] = 1; 
  
        for(int i = 1; i < n; i++){ 
  
            while((!st.empty()) && (price[st.peek()] <= price[i])){ 
                st.pop(); 
            }
  
            S[i] = (st.empty()) ? (i + 1) : (i - st.peek()); 
  
            st.push(i); 
        }  
    } 
  
    static void display(int arr[]){ 
        System.out.print("Span of "+arr.length+" days : "); 
        for (int i = 0; i < arr.length; i++)  
            System.out.print(arr[i]+" ");  
    } 
  
    public static void main(String[] args){ 
        
        int price[] = {100, 80, 60, 70, 60, 75, 85}; 
        int n = price.length; 
        int S[] = new int[n]; 
  
        calSpan(price, n, S); 
  
        display(S); 
    } 
}
Span of 7 days : 1 1 1 2 1 4 6

복잡성 분석

시간 복잡성 : O (n) 여기서 n은 주가가 제공되는 일수입니다.

보조 공간 : O (n) n 주가에 대해 스팬을 저장하기 위해 공간을 사용했기 때문입니다.

참조