買賣股票的最好時機(一)
描述
假設你有一個陣列prices，長度為n，其中prices[i]是股票在第i天的價格，請根據這個價格陣列，回傳買賣股票能獲得的最大收益
1.你可以買入一次股票和賣出一次股票，并非每天都可以買入或賣出一次，總共只能買入和賣出一次，且買入必須在賣出的前面的某一天
2.如果不能獲取到任何利潤，請回傳0
3.假設買入賣出均無手續費
解法一：暴力(常規大回圈解決)
思路步驟：
最顯而易見的解法，當然可能并不是最優的解法
宣告變數ans=0存放最終答案
兩層for回圈，分別找到陣列中最大的差值，表示利潤最大化
比較并更新ans的值
回傳ans即為答案
代碼
int ans = 0;
for (int i = 0; i < prices.length; i++) {
for (int j = i+1; j < prices.length; j++) {
if (prices[j] - prices[i] > ans) {
ans = prices[j] - prices[i];
}
}
}
return ans;
解法二：關于解法一的優化：貪心演算法
思路
我們假設自己購買股票，為了達到利潤最大化，必然會挑一個歷史最低點進行買入,
宣告最低價格minPrices
那么在第i天賣出的股票的利潤就是Prices[i]-minPrices
一趟遍歷記錄最低點即可
代碼
package esay.JZ63買賣股票的最好時機1;
public class Solution {
/**
* @param prices int整型一維陣列
* @return int整型
*/
public int maxProfit(int[] prices) {
// write code here
//1、暴力演算法
/*int ans = 0;
for (int i = 0; i < prices.length; i++) {
for (int j = i+1; j < prices.length; j++) {
if (prices[j] - prices[i] > ans) {
ans = prices[j] - prices[i];
}
}
}
return ans;*/
//2、貪心演算法
int minPrice = Integer.MAX_VALUE;
int ans = 0;
for (int i = 0; i < prices.length; i++) {
if (minPrice > prices[i]) {
minPrice = prices[i];
} else if (prices[i] - minPrice > ans) {
ans = prices[i] - minPrice;
}
}
return ans;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/532527.html
標籤：其他
上一篇：OpenGL ES EAGLContext 和 EGLContext
下一篇：<三>物件的淺拷貝和深拷貝問題