买卖股票的最好时机题解

女爷i 2023-10-04 16:28 47阅读 0赞

描述  
假设你有一个数组，其中第 ***i*** 个元素是股票在第 ***i*** 天的价格。  
你有一次买入和卖出的机会。（只有买入了股票以后才能卖出）。请你设计一个算法来计算可以获得的最大收益。  
示例1  
输入：  
\[1,4,2\]

返回值：  
3

解法一：动态规划

import java.util.*;
    
    
    public class Solution {
        
        /**
         * 
         * @param prices int整型一维数组 
         * @return int整型
         */
        public int maxProfit (int[] prices) {
        
            // write code here
            // 动态规划
            int n = prices.length;
            int[][] dp = new int[n][2];
            dp[0][0] = 0;
            dp[0][1] = -prices[0];
            for (int i = 1; i < n; i++) {
        
                dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
                dp[i][1] = Math.max(dp[i - 1][1], -prices[i]);
            }
            
            return dp[n - 1][0];
        }
    }

优化：

import java.util.*;
    
    
    public class Solution {
        
        /**
         * 
         * @param prices int整型一维数组 
         * @return int整型
         */
        public int maxProfit (int[] prices) {
        
            // write code here
            // 动态规划
            int n = prices.length;
            int hold = -prices[0];
            int nohold = 0;
            
            for (int i = 1; i < n; i++) {
        
                nohold = Math.max(nohold, hold + prices[i]);
                hold = Math.max(hold, -prices[i]);
            }
            
            return nohold;
        }
    }

解法二：双指针  
一个指针记录访问过的最小值（注意这里是访问过的最小值），一个指针一直往后走，然后计算他们的差值，保存最大的即可。

import java.util.*;
    
    
    public class Solution {
        
        /**
         * 
         * @param prices int整型一维数组 
         * @return int整型
         */
        public int maxProfit (int[] prices) {
        
            // write code here
            // 双指针
            if (prices == null || prices.length == 0) {
        
                return 0;
            }
            int min = prices[0], max = 0;
            int n = prices.length;
            for (int i = 1; i < n; i++) {
        
                min = prices[i] < min ? prices[i] : min;
                max = Math.max(prices[i] - min, max);
            }
            return max;
            
        }
    }

解法三：单调栈  
单调栈解决的原理很简单，我们要始终保持栈顶元素是所访问过的元素中最小的，如果当前元素小于栈顶元素，就让栈顶元素出栈，让当前元素入栈。如果访问的元素大于栈顶元素，就要计算他和栈顶元素的差值，我们记录最大的即可。

import java.util.*;
    
    
    public class Solution {
        
        /**
         * 
         * @param prices int整型一维数组 
         * @return int整型
         */
        public int maxProfit (int[] prices) {
        
            // write code here
            // 单调栈
            if (prices == null || prices.length == 0) {
        
                return 0;
            }
            Deque<Integer> stack = new ArrayDeque<Integer>();
            stack.addFirst(prices[0]);
            int max = 0;
            for (int i = 1; i < prices.length; i++) {
        
                if (stack.peekFirst() > prices[i]) {
        
                    stack.pollFirst();
                    stack.addFirst(prices[i]);
                } else {
        
                    max = Math.max(prices[i] - stack.peekFirst(), max);
                }
                
            }
            return max;
            
        }
    }