股票跨度问题


难度级别 中等
经常问 亚马逊 德里韦里 空气质量

这个问题“股票跨度问题”是财务方面的问题。 在这个问题中,我们找到了每天股票价格的股票跨度。 在任何特定日期之前(其前几天的股价小于或等于其股价)的最大连续天数称为跨度。

股票跨度问题

如上图所示的库存跨度问题–

对于第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 1 2 1 4 6

输入: 价格= {10,4,5,90,120,80}

输出: 6天的跨度:1 1 2 4 5 1

不使用堆栈

股票跨度问题的朴素方法

算法

  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

用于股票跨度问题的Java程序

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

复杂度分析

时间复杂度: O(n * n)其中n是给出股票价格的天数。

辅助空间: O(n),因为我们使用空间来存储n个股票价格的跨度。

使用堆栈

解决股票跨度问题的有效方法

算法

  1. 初始化一个数组以存储n天的股票价格。
  2. 创建另一个大小为n的数组S来存储跨度和整数类型的堆栈st。
  3. 从1遍历到n-1,而 不为空并且当前索引的价格大于或等于该索引的价格等于堆栈顶部的值,则弹出顶部。
  4. 更新S []的当前索引,因为当前索引+ 1是堆栈是空的,否则是当前索引–堆栈顶部,并将当前索引推入/插入堆栈中。
  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

用于股票跨度问题的Java程序

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个股票价格的跨度。

參考資料