题目链接：点击打开链接
题目大意：略
解题思路
相关企业
- 字节跳动
- 微软（Microsoft）
- 优步（Uber）
- 谷歌（Google）
- 苹果（Apple）
- 甲骨文（Oracle）
- 彭博（Bloomberg）
- 高盛集团（Goldman Sachs）
- 亚马逊（Amazon）
AC 代码
- Java
// 解决方案(1) class Solution { public int maxProfit(int[] prices) { int cost = Integer.MAX_VALUE, profit = 0; for(int price : prices) { cost = Math.min(cost, price); profit = Math.max(profit, price - cost); } return profit; } } // 解决方案(2) class Solution { public int maxProfit(int[] prices) { if (prices.length == 0) { return 0; } List<Integer> list = new ArrayList<>(); // 当前买入最划算指针 int ptr = 0; list.add(prices[ptr]); int maxn = prices[ptr]; for (int i = 1; i < prices.length; i++) { int num = prices[i]; // 当天卖出大于之前的最大卖出值, 直接找到买入最划算指针 if (num > maxn) { maxn = num; while (ptr + 1 < list.size()) { ptr++; } } // 当天卖出小于等于之前的最大卖出值, 遍历找出是否存在买入最划算候选指针, 比当前还要划算的 else { for (int j = ptr; j < list.size(); j++) { if (num - list.get(j) > maxn - list.get(ptr)) { maxn = num; ptr = j; } } } // 如果比集合最小的还要小, 说明符合买入最划算的候选指针, 使用 LinkedList 则超时, 获取操作你懂的 if (num < list.get(list.size() - 1)) { list.add(num); } } return maxn - list.get(ptr); } }
- C++
class Solution { public: int maxProfit(vector<int>& prices) { int cost = INT_MAX, profit = 0; for(int price : prices) { cost = min(cost, price); profit = max(profit, price - cost); } return profit; } };
