首页 > 其他分享 >力扣——121.买卖股票的最佳时机(C语言)

力扣——121.买卖股票的最佳时机(C语言)

时间:2023-04-22 13:57:16浏览次数:46  
标签:return int max pricesSize C语言 力扣 121 prices diff

title: 力扣——121.买卖股票的最佳时机(C语言)

题目描述:

给定一个数组,它的第 i 个元素是一支给定股票第 i 天的价格。

如果你最多只允许完成一笔交易(即买入和卖出一支股票一次),设计一个算法来计算你所能获取的最大利润。

注意:你不能在买入股票前卖出股票。

示例1:

输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天(股票价格 = 1)的时候买入,在第 5 天(股票价格 = 6)的时候卖出,最大利润 = 6-1 = 5 。
     注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格;同时,你不能在买入前卖出股票。

示例2:

输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

插入代码:

方法1:

时间复杂度O(n^2)

int maxProfit(int* prices, int pricesSize){
    if(NULL==prices || 0==pricesSize || 1==pricesSize){
        return 0;
    }
    int max, tmp;
	int i, j;
	max = prices[1] - prices[0];
	for (i = 0; i < pricesSize; ++i)
	{
		for (j = i+1; j < pricesSize; ++j)
		{
			tmp = prices[j] - prices[i];
			if (tmp > max) {
				max = tmp;
			}
		}
	}
	if (max < 0) {
		return 0;
	}
	return max;
}

执行结果:

通过

执行用时:1204 ms, 在所有 C 提交中击败了6.67%的用户

内存消耗:6.8 MB, 在所有 C 提交中击败了14.46%的用户

方法2:

时间复杂度O(n)

思路:在卖出价固定时,买入价越低获得的利润越大。也就是说,如果在扫描到数组的第i个数字时,只要我们能记住之前i-1个数字中的最小值,就能算出在当前价格卖出时的最大值。

int maxProfit(int* prices, int pricesSize){
    if(NULL==prices || pricesSize<2){
        return 0;
    }
    int min = prices[0];
    int max_diff = prices[1]-prices[0];
    int i, cur_diff;
    for(i=2; i<pricesSize;++i){
        if(prices[i-1] < min){
            min = prices[i-1];
        }
        cur_diff = prices[i] - min;
        if(cur_diff > max_diff){
            max_diff = cur_diff;
        }
    }
    if(max_diff < 0){
        return 0;
    }
    return max_diff;
}

执行结果:

通过

执行用时:8 ms, 在所有 C 提交中击败了73.10%的用户

内存消耗:6.5 MB, 在所有 C 提交中击败了52.47%的用户

标签:return,int,max,pricesSize,C语言,力扣,121,prices,diff
From: https://www.cnblogs.com/blue-Suri/p/17342936.html

相关文章

  • 力扣——193.有效电话号码(shell)
    title:力扣——193.有效电话号码(shell)给定一个包含电话号码列表(一行一个电话号码)的文本文件file.txt,写一个bash脚本输出所有有效的电话号码。你可以假设一个有效的电话号码必须满足以下两种格式:(xxx)xxx-xxxx或xxx-xxx-xxxx。(x表示一个数字)你也可以假设每行前后没有......
  • 力扣——192.统计词频(shell)
    title:力扣——192.统计词频(shell)题目描述:写一个bash脚本以统计一个文本文件words.txt中每个单词出现的频率。为了简单起见,你可以假设:words.txt只包括小写字母和''。每个单词只由小写字母组成。单词间由一个或多个空格字符分隔。示例:假设words.txt内容如下:th......
  • 力扣——195.第十行(shell)
    title:力扣——195.第十行(shell)给定一个文本文件file.txt,请只打印这个文件中的第十行。示例:假设file.txt有如下内容:Line1Line2Line3Line4Line5Line6Line7Line8Line9Line10你的脚本应当显示第十行:Line10方法1:awk'NR==10'file.txt方法2:tai......
  • 力扣——240.搜索二维数组II(c语言)
    title:力扣——240.搜索二维数组II(c语言)同《剑指offer》04题目描述:编写一个高效的算法来搜索mxn矩阵matrix中的一个目标值target。该矩阵具有以下特性:每行的元素从左到右升序排列。每列的元素从上到下升序排列。示例1:输入:matrix=[[1,4,7,11,15],[2,5,8,12,19],......
  • 力扣——5.最长回文子串(c语言)
    题目描述:给定一个字符串s,找到s中最长的回文子串。你可以假设s的最大长度为1000。示例1:输入:"babad"输出:"bab"注意:"aba"也是一个有效答案。示例2:输入:"cbbd"输出:"bb"1、思路1:动态规划对于一个子串而言,如果它是回文子串,并且长度大于2,那么将它首尾两个字......
  • C语言和C++的switch语句用法
    C语言和C++的switch语句用法是相似的,但在一些细节上有所不同。在C语言中,switch语句的用法如下:switch(expression){  caseconstant1:    //dosomething    break;  caseconstant2:    //dosomething    break;  //...  ......
  • C语言常见的加密库
    C语言加密库有很多,以下是一些常见的加密库:OpenSSL:一个功能强大的开源加密库,提供了各种加密算法和协议的实现,包括对称加密、公钥加密、数字签名和证书管理等。Libsodium:一个现代化的加密库,提供了高级加密、公钥加密、哈希函数等,被广泛用于网络通信、存储和加密货币等领域。Bota......
  • 编程打卡:C语言趣味编程习题做
    编程打卡:C语言趣味编程习题做完数问题描述完数是因子相加等于它本身的数字,求一个范围内的完数。设计思路遍历这个范围内的数字,求它的因子,然后判断是否为完数即可。流程图graphA[开始]-->B[inputN,i=2]-->C{i<=N}--Yes-->D[j=1,sum=0]-->E{j<=i/2}--Yes-->F{i%j==0}--Yes--......
  • [每天例题]蓝桥杯 C语言 方阵
    方阵题目思路分析使用for循环,将k逐渐增大,if判断最大值的k代码#include<stdio.h>intmain(){ longlongintn,k,max; scanf("%d",&n); if((n>=2)&&(n<=100000000)) { for(k=1;k<=n;k++) { if((k*k)<=n) { max=k; } } }......
  • windows桌面应用程序框架C语言
    #ifdefined(UNICODE)&&!defined(_UNICODE)#define_UNICODE#elifdefined(_UNICODE)&&!defined(UNICODE)#defineUNICODE#endif#include<tchar.h>#include<windows.h>/*DeclareWindowsprocedure*/LRESULTCALLBAC......