股票收益问题

2024年8月28日 | 14 分钟阅读

“股票跨度问题”属于金融领域。此问题旨在确定每日股票价格的跨度。其跨度是指在任何给定日期之前，股票价格小于或等于该日价格的最大连续天数。

股票价格在某一天的跨度 Si 被描述为：紧接在该日之前，当日股价小于或等于其之前价格的最大连续天数。

例如，如果提供一个为期七天的价格数组为 100, 80, 60, 70, 60, 75, 85，则这七天的跨度值分别为 1, 1, 1, 2, 1, 4, 6。

有两种方法可以解决这个股票跨度问题。这两种方法是：

低效方法
高效方法

在解决这个股票跨度问题时，需要遍历输入的价格数组。当左侧的项较小时，遍历左侧的元素，并增加每个被访问元素的跨度值。

现在，让我们借助用三种不同编程语言（C++、Java 和 Python）编写的代码来理解股票跨度问题。

C++ 代码

让我们通过以下 C++ 代码来理解这个问题。

// A sample C++ program to calculate stock span values  
#include <bits/stdc++.h> 
using namespace std;   
// Fills array S[] with span values  
void calculateSpan(int price[], int n, int S[])  
{  
    // Span value of first day is always 1  
    S[0] = 1;   
    // Calculate span value of remaining days   
    // by linearly checking previous days  
    for (int i = 1; i < n; i++)  
    {  
        S[i] = 1; // Initialize span value   
        // Traverse left while the next element   
        // on left is smaller than price[i]  
        for (int j = i - 1; (j >= 0) &&  
                (price[i] >= price[j]); j--)  
            S[i]++;  
    }  
}   
// A utility function to print elements of array  
void printArray(int arr[], int n)  
{  
    for (int i = 0; i < n; i++)  
        cout << arr[i] << " ";  
}    
// Driver code  
int main()  
{  
    int size_arr = 0;
    cout<<"Enter the size of the span array::\n";
    cin>>size_arr;
    int price[size_arr]; //= new int[size_arr];//{ 10, 4, 5, 90, 120, 80 };  
    int n = size_arr;//sizeof(price) / sizeof(price[0]);  
    int S[n];  
    int data;
    int count = 0;
      char ch;
            // Do-while loop
            // Do part for performing actions
            do
            // Menu is displayed
            // Users enter 'y' to continue 'n' if
            // entered by user , the program terminates
            {
                  // Menu
                  // Display messages
                  cout<<"Please Choose one of the Operations listed below::\n";
                  cout<<"1. To Insert a new span value to the array.\n";
                  cout<<"2. To Calculate span value entered in array.\n";
                  cout<<"3. To Display the Calculated span values.\n";
                  cout<<"\n";               
                  int choice;
                  scanf("%d",&choice);
                  // Switch case
                  switch (choice) {
                  // Case 1
                  case 1:
                        cout<<"Enter the span value that you want to add to array :\n";
                        cin>>data;                        
                        price[count++] = data;
                        // Display message
                        cout<<"Data Added Successfully.\n";
                        // Break statement to terminate a case
                        break;
                  // Case 2
                  case 2:
                        // Display message
                        calculateSpan(price, n, S);
                        cout<<"Span Values Calculated Successfully.";
                        // Break statement to terminate a case
                        break;
                  // Case 3
                  case 3:
                        // Display message
                        cout<<"New calculated Span values:\n";
                        printArray(S,n);
                        // Break statement to terminate a case
                        break;
                  default:
                        // Print statement
                        cout<<"Please enter a valid option from the menu to proceed further.\n \n";
                        // Break statement
                        break;
                  }
                  cout<<"\nType [N or n] to terminate the program.\nType [Y or y] to continue the program.\n";
                  cin>>ch;                 
            } while (!(ch == 'N' || ch == 'n'));
    return 0;  
}

输出

上述代码给出以下输出。

Enter the size of the span array::
7
Please Choose one of the Operations listed below::
1. To Insert a new span value into the array.
2. To Calculate span value entered in array.
3. To Display the Calculated span values.
1
Enter the span value that you want to add to the array :
16
Data Added Successfully.
Type [N or n] to terminate the program.
Type [Y or y] to continue the program.
y
Please Choose one of the Operations listed below::
1. To Insert a new span value into the array.
2. To Calculate span value entered in array.
3. To Display the Calculated span values.
1
Enter the span value that you want to add to the array :
67
Data Added Successfully.
Type [N or n] to terminate the program.
Type [Y or y] to continue the program.
y
Please Choose one of the Operations listed below::
1. To Insert a new span value into the array.
2. To Calculate span value entered in array.
3. To Display the Calculated span values.
1
Enter the span value that you want to add to the array :
44
Data Added Successfully.
Type [N or n] to terminate the program.
Type [Y or y] to continue the program.
y
Please Choose one of the Operations listed below::
1. To Insert a new span value into the array.
2. To Calculate span value entered in array.
3. To Display the Calculated span values.
1
Enter the span value that you want to add to the array :
93 
Data Added Successfully.
Type [N or n] to terminate the program.
Type [Y or y] to continue the program.
y
Please Choose one of the Operations listed below::
1. To Insert a new span value into the array.
2. To Calculate span value entered in array.
3. To Display the Calculated span values.
1
Enter the span value that you want to add to the array :
33
Data Added Successfully.
Type [N or n] to terminate the program.
Type [Y or y] to continue the program.
y
Please Choose one of the Operations listed below::
1. To Insert a new span value into the array.
2. To Calculate span value entered in array.
3. To Display the Calculated span values.
1
Enter the span value that you want to add to the array :
2
Data Added Successfully.
Type [N or n] to terminate the program.
Type [Y or y] to continue the program.
y
Please Choose one of the Operations listed below::
1. To Insert a new span value into the array.
2. To Calculate span value entered in array.
3. To Display the Calculated span values.
1
Enter the span value that you want to add to the array :
86
Data Added Successfully.
Type [N or n] to terminate the program.
Type [Y or y] to continue the program.
y
Please Choose one of the Operations listed below::
1. To Insert a new span value into the array.
2. To Calculate span value entered in array.
3. To Display the Calculated span values.
2
Span Values Calculated Successfully.
Type [N or n] to terminate the program.
Type [Y or y] to continue the program.
y
Please Choose one of the Operations listed below::
1. To Insert a new span value into the array.
2. To Calculate span value entered in array.
3. To Display the Calculated span values.
3
New calculated Span values:
1 2 1 4 1 1 3 
Type [N or n] to terminate the program.
Type [Y or y] to continue the program.
n

在上面的 C++ 代码中，我们创建了一个类，该类包含计算所插入股票价格跨度值的函数。代码的流程如下：用户有三个选择：添加股票价格，为这些插入的股票价格计算跨度值，然后打印计算出的股票价格跨度值。用户输入股票价格；价格成功添加后，调用 calculateSpan() 函数，该函数为插入的价格值计算跨度值。最后，通过最后一个选项打印这些跨度值。

Java 代码

让我们也借助 Java 代码来理解这个问题。

// A sample Java program to calculate stock span values  
import java.util.Arrays; 
import java.util.Stack;
import java.util.Scanner; 
class spanStock{ 
    // A function named calSpan() is written that will be used to calculate the span of the prices of the stocks that are stored in the price array, and those calculated spans corresponding to each price is stored in the integer array S
    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); 
        }  
    } 
    // A function named display() is written that will be used to print the spans of the prices that are calculated by the calSpan() function
    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]+" ");  
    } 
// Main function is written to call the calSpan() function that will be used to calculate the span of the prices of the stocks that are stored in the price array, and those calculated spans corresponding to each price is stored in the integer array S
    public static void main(String[] args){        
        Scanner scan = new Scanner(System.in);
        System.out.println("Enter the size of the span array:: \n");
        int size_arr = scan.nextInt();
        int price[] = new int[size_arr]; 
	int price[] = new int[size_arr]; 
        int n = price.length; 
        int S[] = new int[n];         
        char ch;
        int data;
        int count = 0;
       /*  Perform list operations  */
        do
            {
                System.out.println("Please Choose one of the Operations listed below::");
                System.out.println("1. To Insert a new price value into the array.");
                System.out.println("2. To Calculate span value entered in array.");
                System.out.println("3. To Display the Calculated span values.");
                int choice = scan.nextInt();
                switch (choice)
                    {
                    case 1 :                       
                        System.out.println("Enter the price value that you want to add to the array :\n");
                        data = scan.nextInt();
                        price[count++] = data;
                        // Display message
                        System.out.println("Data Added Successfully.\n");
                        // Break statement to terminate a case
                        break;
                    case 2 :
                        System.out.println("Span Values Calculated Successfully.");
                        calSpan(price,n,S);                
                        break;
                    case 3:
                        System.out.println("New calculated Span values");
                        display(S);
                        break;
                    default :
                        System.out.println("Wrong Entry\n ");
                        break;
                    }
                System.out.println("\nDo you want to continue (Type y or n)\n");
                ch = scan.next().charAt(0);
            }
        while (ch == 'Y'|| ch == 'y');
    } 
}

输出

上面的 Java 代码产生以下输出。

Enter the size of the span array:: 
9
Please Choose one of the Operations listed below::
1. To Insert a new price value into the array.
2. To Calculate span value entered in array.
3. To Display the Calculated span values.
1
Enter the price value that you want to add to the array :
14
Data Added Successfully.
Do you want to continue (Type y or n)
y
Please Choose one of the Operations listed below::
1. To Insert a new price value into the array.
2. To Calculate span value entered in array.
3. To Display the Calculated span values.
1
Enter the price value that you want to add to the array :
287
Data Added Successfully.
Do you want to continue (Type y or n)
y
Please Choose one of the Operations listed below::
1. To Insert a new price value into the array.
2. To Calculate span value entered in array.
3. To Display the Calculated span values.
1 
Enter the price value that you want to add to the array :
32
Data Added Successfully.
Do you want to continue (Type y or n)
y
Please Choose one of the Operations listed below::
1. To Insert a new price value into the array.
2. To Calculate span value entered in array.
3. To Display the Calculated span values.
1
Enter the price value that you want to add to the array :
40
Data Added Successfully.
Do you want to continue (Type y or n)
y
Please Choose one of the Operations listed below::
1. To Insert a new price value into the array.
2. To Calculate span value entered in array.
3. To Display the Calculated span values.
1
Enter the price value that you want to add to the array :
533
Data Added Successfully.
Do you want to continue (Type y or n)
y
Please Choose one of the Operations listed below::
1. To Insert a new price value into the array.
2. To Calculate span value entered in array.
3. To Display the Calculated span values.
1
Enter the price value that you want to add to the array :
6
Data Added Successfully.
Do you want to continue (Type y or n)
y
Please Choose one of the Operations listed below::
1. To Insert a new price value into the array.
2. To Calculate span value entered in array.
3. To Display the Calculated span values.
1
Enter the price value that you want to add to the array :
700
Data Added Successfully.
Do you want to continue (Type y or n)
y
Please Choose one of the Operations listed below::
1. To Insert a new price value into the array.
2. To Calculate span value entered in array.
3. To Display the Calculated span values.
1
Enter the price value that you want to add to the array :
855
Data Added Successfully.
Do you want to continue (Type y or n)
y
Please Choose one of the Operations listed below::
1. To Insert a new price value into the array.
2. To Calculate span value entered in array.
3. To Display the Calculated span values.
1
Enter the price value that you want to add to the array :
9002
Data Added Successfully.
Do you want to continue (Type y or n)
y
Please Choose one of the Operations listed below::
1. To Insert a new price value into the array.
2. To Calculate span value entered in array.
3. To Display the Calculated span values.
2
Span Values Calculated Successfully.
Do you want to continue (Type y or n)
y
Please Choose one of the Operations listed below::
1. To Insert a new price value into the array.
2. To Calculate span value entered in array.
3. To Display the Calculated span values.
3
New calculated Span values.
Span of 9 days : 1 2 1 2 5 1 7 8 9 
Do you want to continue (Type y or n)
n

在上面的 Java 代码中，我们创建了一个类，该类包含计算所插入股票价格跨度值的函数。代码的流程如下：用户有三个选择：添加股票价格，为这些插入的股票价格计算跨度值，然后打印计算出的股票价格跨度值。现在，用户输入股票价格。价格成功添加后，调用 calculateSpan() 函数，该函数为插入的价格值计算跨度值。最后，通过最后一个选项打印这些跨度值。

Python

现在我们通过这段 Python 代码来找到这个问题的解决方案。

# A sample Python program to calculate stock span values  
class StackSpanProblem:
	# A function named calculateSpan() will be used to calculate the span of the prices of the stocks that are stored in the price array, and those calculated spans corresponding to each price is stored in the integer array S
	def calculateSpan(self,price, n, S):		
		# Span value of first day is always 1
		S[0] = 1
		# Calculate span value of remaining days by linearly
		# checking previous days
		for i in range(1, n, 1):
			S[i] = 1 # Initialize span value	 
			# Traverse left while the next element on left is
			# smaller than price[i]
			j = i - 1
			while (j>= 0) and (price[i] >= price[j]) :
						S[i] += 1
						j -= 1							
	# A utility function to print elements of array
	def printArray(self,arr, n):
		for i in range(n):
			print(arr[i], end = " ")
# Driver program to test above function
price = list()
while True:
	print("Please Choose one of the Operations listed below::")
	print("1. To Insert a new price value into the array.")
	print("2. To Calculate span value entered in array.")
	print("3. To Display the Calculated span values.")
	choice = input()
	if choice==1:
		print("Enter the price value that you want to add to the array :")
		price.append(input())
	elif choice==2:
		calculateSpan(price,len(price),S)
	elif choice==3:
		printArray(S,len(price))
	else:
		print("Inavlid Entry")
	print("Do you want to continue (Type y or n)")
	choice_cont = input()
	if choice_cont=='n':
		break

输出

以上 Python 代码产生以下输出。

Enter the size of the span array::
7
Please Choose one of the Operations listed below::
1. To Insert a new span value into the array.
2. To Calculate span value entered in array.
3. To Display the Calculated span values.
1
Enter the span value that you want to add to the array :
16
Data Added Successfully.
Type [N or n] to terminate the program.
Type [Y or y] to continue the program.
y
Please Choose one of the Operations listed below::
1. To Insert a new span value into the array.
2. To Calculate span value entered in array.
3. To Display the Calculated span values.
1
Enter the span value that you want to add to the array :
67
Data Added Successfully.
Type [N or n] to terminate the program.
Type [Y or y] to continue the program.
y
Please Choose one of the Operations listed below::
1. To Insert a new span value into the array.
2. To Calculate span value entered in array.
3. To Display the Calculated span values.
1
Enter the span value that you want to add to the array :
44
Data Added Successfully.
Type [N or n] to terminate the program.
Type [Y or y] to continue the program.
y
Please Choose one of the Operations listed below::
1. To Insert a new span value into the array.
2. To Calculate span value entered in array.
3. To Display the Calculated span values.
1
Enter the span value that you want to add to the array :
93 
Data Added Successfully.
Type [N or n] to terminate the program.
Type [Y or y] to continue the program.
y
Please Choose one of the Operations listed below::
1. To Insert a new span value into the array.
2. To Calculate span value entered in array.
3. To Display the Calculated span values.
1
Enter the span value that you want to add to the array :
33
Data Added Successfully.
Type [N or n] to terminate the program.
Type [Y or y] to continue the program.
y
Please Choose one of the Operations listed below::
1. To Insert a new span value into the array.
2. To Calculate span value entered in array.
3. To Display the Calculated span values.
1
Enter the span value that you want to add to the array :
2
Data Added Successfully.
Type [N or n] to terminate the program.
Type [Y or y] to continue the program.
y
Please Choose one of the Operations listed below::
1. To Insert a new span value into the array.
2. To Calculate span value entered in array.
3. To Display the Calculated span values.
1
Enter the span value that you want to add to the array :
86
Data Added Successfully.
Type [N or n] to terminate the program.
Type [Y or y] to continue the program.
y
Please Choose one of the Operations listed below::
1. To Insert a new span value into the array.
2. To Calculate span value entered in array.
3. To Display the Calculated span values.
2
Span Values Calculated Successfully.
Type [N or n] to terminate the program.
Type [Y or y] to continue the program.
y
Please Choose one of the Operations listed below::
1. To Insert a new span value into the array.
2. To Calculate span value entered in array.
3. To Display the Calculated span values.
3
New calculated Span values:
1 2 1 4 1 1 3 
Type [N or n] to terminate the program.
Type [Y or y] to continue the program.
n

在上面的 Python 代码中，我们创建了一个类，该类包含计算所插入股票价格跨度值的函数。代码的流程如下：用户有三个选择：添加股票价格，为这些插入的股票价格计算跨度值，然后打印计算出的股票价格跨度值。现在，用户输入股票价格。价格成功添加后，调用 calculateSpan() 函数，该函数为插入的价格值计算跨度值。最后，通过最后一个选项打印这些跨度值。

下一个主题树堆数据结构

股票收益问题

C++ 代码

Java 代码

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

数据结构教程

DS 数组

DS 链表

DS 栈

DS 队列

DS 树

DS 图

DS 搜索

DS 排序

哈希与堆

差异

二叉树

二叉搜索树

AVL 树

单向链表

双向链表

循环链表

循环双向链表

DS 选择题

其他

股票收益问题

C++ 代码

Java 代码

相关帖子

给定父数组时 N 元树的高度

Merkle 树和哈希链数据结构的区别

第 k1 小和第 k2 小元素之间的所有元素之和

最小化数组中的偏差

设计和实现特殊栈数据结构

一副牌中的 X 种类型

与给定数字最接近的三元组和

二叉搜索树 vs 三元搜索树

左右两侧下一个更大元素的索引的最大乘积

给定数组 A[] 和数字 x，检查 A[] 中是否存在和为 x 的对 (也称为两数之和)

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器