`
ouqi
  • 浏览: 41200 次
  • 性别: Icon_minigender_2
  • 来自: 北京
社区版块
存档分类
最新评论

[leetcode]Best Time to Buy and Sell Stock

 
阅读更多

Best Time to Buy and Sell Stock

Say you have an array for which the ith element is the price of a given stock on day i.

 

If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

一开始思路:

对于第i天,如果选择在这一天卖出的话,考虑在什么时候买入合适? 思考发现 一定是在[0,i]范围内的价格最低的那一天买入最合适。

那我们

  1. 初始化最大利润maxProfit = 0;
  2. 遍历prices数组,过程中记录价格最小值min.当遍历到第i天的时候 min一定是在[0,i]范围内的,比较prices[i]-min和max的大小 max取两者中的最大值

ps: 期间还想过其实没必要考虑每一天卖出的情况,在一个单调序列[i,j]中 计算第i天卖出时min下标<=i;而在计算第j天卖出时 min下标同样<=i.所以第j天卖出肯定比第i天卖出利润大,遍历的时候可以直接考虑单调递增序列的尾部天数卖出。但是感觉复杂度没啥改进,还是要遍历整个数组,而且写起来更加复杂,所以想想还是之前的比较好。

 

后来想用动态规划,定义c[i]表示[0,i]范围内的maxProfit,min为[0,i-1]范围内的最小值

则有

  1. 初始c[0] = 0;
  2. 当prices[i]<min时: 即当前值比前面的最小值还要小,则c[i] = c[i-1];并且把min赋值为prices[i];
  3. 当prices[i]>=min时: c[i] = max{c[i-1],prices[i]-min};
  4. 我们要求的maxProfit = c[len-1];

后来一想似乎没必要用数组c去保存因为c[i]肯定是大于等于c[i-1]。所以用一个变量max记录就可以。然后代码写出来,发现跟最开始的思路是一样的-。-

 

 

 public int maxProfit(int[] prices) {
        // Start typing your Java solution below
        // DO NOT write main() function
          if(prices == null || prices.length == 0)  return 0;
             int len = prices.length;
	        
	         int max = 0;
	         int min = prices[0];
	         
	         for(int i = 1;i<=len-1;i++){
	             if(prices[i]<min) {min = prices[i];}
	             else max = prices[i]-min>max? prices[i]-min:max;
	         }
             return max;
    }

 

Best Time to Buy and Sell Stock II

与上题的区别在于可以交易n次,算最大利润

 

直观的想法就是在价格数组prices[]的所有单调序列的头(最低点)买入,尾(最高点)卖出;

 

然后就想有没有可能不按照上述规则算出的利润更大呢?思考了下,发现不可能

  1. 对于单调序列内部的买入卖出不难思考 ,肯定是头买入,尾卖出最高。
  2. 那考虑跨越单调序列的买入卖出:
  3.  假设[i, k]  [k+1, j] 是两个相邻的单调区间,我们在[i , k]内的某一点 x 买入,在[k+1, j ]内的某一点y卖出,首先当x  = i和y = j时,是这种买入卖出方式的最大值(因为x不等于i的话,x-1买入肯定比x买入收益更大,y的取值类似)。 那么比较在i点买入,j点卖出和在i点买入,k点卖出,k+1点买入,j点卖出的利润大小:因为分为了两个单调区间,所以price[k+1]<price[k] 根据这个条件可以证明: prices[j] - prices[i] <prices[j] - prices[k+1] + prices[k] - prices[i] 所以第二种方式i点买入,k点卖出,k+1点买入,j点卖出的利润更大。

代码:

 

  public int maxProfit(int[] prices) {
        // Start typing your Java solution below
        // DO NOT write main() function
       if(prices == null || prices.length == 0) return 0;
       int i = 0;
       int min,max;
       int maxProfit = 0;
       int len =  prices.length;
       
       while(i<=len-1){
           min = prices[i];
           max = prices[i];
           i++;
           while(i<=len-1&&prices[i]>=prices[i-1]) i++;
           max = prices[i-1];
           maxProfit = maxProfit + max - min;
       }
       return maxProfit;
    }

 

Best Time to Buy and Sell Stock III

这个的限制就是交易最多2次

刚开始就是想的先确定[0,i]范围内的maxProfit,然后算[i,len-1]范围内的maxProfit 求和,取和中的最大值。

然后就在纠结扫一遍 扫到[0,i]的时候,[0,i]范围内的maxProfit好确定,但是[i,len-1]范围内的觉得不好算。

然后发现自己脑残了...为啥一定要纠结同步确定呢,我扫两遍,第一遍从头到尾把[0,i]范围内的最大确定,像

Best Time to Buy and Sell Stock中那样记录为数组c, 第二遍从尾到头扫,在算出[i,len-1]范围内的最大值之后,直接去数组c中取出[0,i-1]范围内的就可以了...

代码:

 

  public int maxProfit(int[] prices) {
	        // Start typing your Java solution below
	        // DO NOT write main() function
	       if(prices == null || prices.length == 0)  return 0;
	         int len = prices.length;
	        
	         int c[] = new int[len];//c[i] means max in interval[0,i] 
	         c[0] = 0;
	         int min = prices[0];
	         
	         for(int i = 1;i<=len-1;i++){
	             if(prices[i]<min) {min = prices[i];c[i] =c[i-1];}
	             else c[i] = prices[i]-min>c[i-1]? prices[i]-min:c[i-1];
	         }
	         int maxProfit = c[len-1];
	         int max = 0;
	        
	        int diff = 0;
	        int tempMax = 0;
	         for(int j = len-1;j>=0;j--){
	             if(prices[j]>max) {max = prices[j];}
	             else if( max-prices[j]>diff) diff = max - prices[j];
	             if(j>=1) tempMax = diff+c[j-1];
	             if(tempMax>maxProfit) maxProfit = tempMax;
	             
	         }
	         
	         return maxProfit;   
	    }

 

 

 

 

 

 

 

 

 

分享到:
评论

相关推荐

    leetcode题目:Best Time to Buy and Sell Stock II

    leetcode题目:Best Time to Buy and Sell Stock II

    lrucacheleetcode-LeetCode:CppSourceCode的LeetCode解决方案

    leetcode LeetCode 解决题目的总数: 136/1753 微信公众号: 工程师Ruojhen 算法-动态规划 题号 名称 English Name 题解 53 最大子序和 Maximum Subarray 70 爬楼梯 Climbing Stairs 121 买卖股票的最佳时机 Best Time...

    javalruleetcode-leetcode-java:力码笔记

    leetcode leetcode-java leetcode刷题笔记 已做题目列表 1.Two Sum 3.Longest Substring Without Repeating Characters 5.Longest Palindromic Substring 20.Valid Parentheses 26.Remove Duplicates from Sorted ...

    股票收益leetcode-leetcode:leetcode摘要

    股票收益leetcode LeetCode 股票问题 Best Time to Buy and Sell Stock (Easy) 一次交易,找最大收益 for i in prices: low = min(low, i) profit = max(profit, i-low) Best Time to Buy and Sell Stock II (Easy) ...

    Andy619-Zhu#CS-Notes-chu#63. 股票的最大利润1

    63. 股票的最大利润题目链接Leetcode:121. Best Time to Buy and Sell Stock题目描述可以有一次买入和一次卖出,买入必

    leetcode分类-LeetCode:力码

    leetcode 分类 LeetCode LeetCode Java Solution 2018年5月31日 更新 最近刷了一遍 LeetCode,发现第一次的代码确实有些 low 很多代码并不简洁,本来1行的代码可以写成3行 思维混乱 没有按照题目类型分类 没有写结题...

    LeetCode:LeetCode Java解决方案

    公众号 coding 笔记、点滴记录,以后的文章也会...最近花时间分门别类整理了 LeetCode 的前 500 题,把相似的题目都放在了一起,比如Best Time to Buy and Sell Stock的6道题,这些题目放在一起刷效果更好。 简书博客:

    cpp-算法精粹

    Best Time to Buy and Sell Stock with Cooldown Interleaving String Scramble String Minimum Path Sum Edit Distance Decode Ways Distinct Subsequences Word Break Word Break II Dungeon Game House Robber ...

    Leetcode的ac是什么意思-LeetCodeInJava:leetcode-java

    Leetcode的ac是什么意思 LeetCodeInJava List #98 Validate Binary Search Tree #100 Same Tree #104 Maximum Depth of Binary Tree #122 Best Time to Buy and Sell Stock II #136 Single Number #150 Evaluate ...

    LeetCode:Leetcode-解决方案

    Best Time to Buy and Sell Stock [121]3. Climbing Stairs [70]4. Maximum Subarray [53]5. House Robber [198]6. Range Sum Query - Immutable [303]7. Counting Bits [338]8. Palindromic Substrings [647]9. ...

    leetcode小岛出水口-leetcode:leetcode训练

    leetcode小岛出水口 leetcode training one problem on file 为了方便文档管理,项目逐渐文档化,以单个文件作为集合最小集。 go语言不能完全适合写算法题 后续会尽可能加入rust或者c的题解 清单 0965. Univalued ...

    leetcode卡-leetcode:利特码解决方案

    leetcode卡 leetcode exercises 3-5 solutions everyday. fighting~ TODO array Best Time to Buy and Sell Stock II Valid Sudoku linked list Palindrome linked list Linked List Cycle trees Convert Sorted ...

    leetcode浇花-LCSolutions:我的力扣解决方案

    leetcode 浇花力扣解决方案 简单的 #0001 - Two Sum #0007 - Reverse Integer #0009 - Palindrome Number #0035 - Search Insert Position #0058 - Length of Last Word #0066 - Plus One #0083 - Remove Duplicates...

    股票买卖最佳时机leetcode-best-time-to-buy-and-sell-stock:让我们弄清楚什么时候买一些股票!这不应该在现

    股票买卖最佳时机leetcode GitFitCode 配对编码挑战! 买卖股票的最佳时机 让我们弄清楚什么时候买一些股票! 这不应该在现实生活中使用。 现在不管你认为你的算法有多好:)。 我确实鼓励您选择一只您感兴趣的股票,...

    lrucacheleetcode-LeetCode_30Day:力扣30天挑战赛

    lru缓存leetcode 力扣_30天 力扣 30 天挑战赛 日 问题描述 问题和解决方案链接 Git 解决方案页面 1 SINGLE NUMBER 2 HAPPY NUMBER 3 MAXIMUM SUBARRAY 4 Move Zeroes 5 Best Time to Buy and Sell Stock II 6 GROUP ...

    leetcode-leetcode:leetcode的最佳C++解决方案

    leetcode leetcode The optimum C++ solutions for the leetcode 这是我自己写的leetcode的题解,目前已经完成了70%左右,后续部分会很快更新 这里放上来的代码都能保证是最优解(复杂度最优) 当然有些题目因为测试...

    LeetCode最全代码

    201 | [Bitwise AND of Numbers Range](https://leetcode.com/problems/bitwise-and-of-numbers-range/) | [C++](./C++/bitwise-and-of-numbers-range.cpp) [Python](./Python/bitwise-and-of-numbers-range.py) | _...

    leetcode答案-LeetCode-Trip:LeetCode刷题代码,大佬勿入

    leetcode 答案 LeetCode-Trip LeetCode刷题代码,大佬勿入。 为一年后的研究生找工作准备 目标是BAT的算法岗哈哈哈哈哈 争取做到每日一更 嗯…… 19.10.22:鸽了这么久,我又回来了……主要在实验室天天没啥事,过于...

    圆和矩形是否重叠leetcode-leetcode_solutions:leetcode_solutions

    圆和椭圆重叠leetcode ——#158 尖端 关心特殊情况 从不同的方向思考 简单的 大批 1.Two Sum -&gt; 使用哈希表避免遍历列表448.查找数组中消失的所有数字-&gt; 1.建立缓冲区来计算数字| 2.使用数组作为带符号的缓冲区118....

    leetcode中文版-leetcode:leetcode

    leetcode中文版车鸟 一组用python编写的算法。 种类 ...best_time_to_buy_and_sell_stock_II binary_tree_inorder_traversal binary_tree_level_order_traversal binary_tree_level_order_traversal_I

Global site tag (gtag.js) - Google Analytics