Priority
121. 买卖股票的最佳时机
给定一个数组，它的第 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。
方法一:暴力法: 时间复杂度O(n^2), 空间复杂度O(1)
public int maxProfit(int prices[]) { int maxprofit = 0; for (int i = 0; i < prices.length - 1; i++) { for (int j = i + 1; j < prices.length; j++) { int profit = prices[j] - prices[i]; if (profit > maxprofit) { maxprofit = profit; } } } return maxprofit; }方法二:时间复杂度O(n), 空间复杂度O(1) [7,1,5,3,6,4]
public int maxProfit(int prices[]) { int minprice = Integer.MAX_VALUE; int maxprofit = 0; for (int i = 0; i < prices.length; i++) { if (prices[i] < minprice) { minprice = prices[i]; }else if (prices[i] - minprice > maxprofit) { maxprofit = prices[i] - minprice; } } return maxprofit; }122. 买卖股票的最佳时机 II
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。 设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。 示例 1: 输入: [7,1,5,3,6,4] 输出: 7 解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。 随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 示例 2: 输入: [1,2,3,4,5] 输出: 4 解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。 注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。 因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。 示例 3: 输入: [7,6,4,3,1] 输出: 0 解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
方法一: 暴力法 复杂度分析 时间复杂度：O(n^n) 调用递归函数 n^n次。 空间复杂度：O(n)，递归的深度为 n。
public int maxProfit(int[] prices) { return calculate(prices, 0); } public int calculate(int[] prices, int s) { if (s >= prices.length) return 0; int max = 0; for (int start = s; start < prices.length - 1; start++) { int maxprofit = 0; for (int i = start + 1; i < prices.length; i++) { if (prices[start] < prices[i]) { int profit = calculate(prices, i + 1) + prices[i] - prices[start]; if (profit > maxprofit) { maxprofit = profit; } } } if (maxprofit > max) { max = maxprofit; } } return max; }方法二 峰谷法 [7, 1, 5, 3, 6, 4] 时间复杂度：O(n) 空间复杂度：O(1)
public int maxProfit(int[] prices) { int i = 0; int valley = prices[0]; int peak = prices[0]; int maxprofit = 0; while (i < prices.length - 1) { while (i < prices.length - 1 && prices[i] >= prices[i + 1]) { i++; } valley = prices[i]; while (i < prices.length - 1 && prices[i] <= prices[i + 1]) { i++; } peak = prices[i]; maxprofit += peak - valley; } return maxprofit; }方法三
public int maxProfit(int[] prices) { int maxprofit = 0; for (int i = 1; i < prices.length; i++) { if (prices[i] > prices[i - 1]) { maxprofit += prices[i] - prices[i - 1]; } } return maxprofit; }239. 滑动窗口最大值
给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。 返回滑动窗口中的最大值。 进阶： 你能在线性时间复杂度内解决此题吗？ 示例: 输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3 输出: [3,3,5,5,6,7] 解释: 滑动窗口的位置 最大值 [1 3 -1] -3 5 3 6 7 3 1 [3 -1 -3] 5 3 6 7 3 1 3 [-1 -3 5] 3 6 7 5 1 3 -1 [-3 5 3] 6 7 5 1 3 -1 -3 [5 3 6] 7 6 1 3 -1 -3 5 [3 6 7] 7 提示： 1 <= nums.length <= 10^5 -10^4 <= nums[i] <= 10^4 1 <= k <= nums.length
方法一: 暴力法 最简单直接的方法是遍历每个滑动窗口，找到每个窗口的最大值。一共有 N - k + 1 个滑动窗口，每个有 k 个元素，于是算法的时间复杂度为 O(Nk),空间复杂度：O(N−k+1)，用于输出数组。
public int[] maxSlidingWindow(int[] nums, int k) { int n = nums.length; if (n * k == 0) return new int[0]; int[] output = new int[n - k + 1]; for (int i = 0; i < n - k + 1; i++) { int max = Integer.MIN_VALUE; for (int j = i; j < k + i; j++) { max = Math.max(max, nums[j]); } output[i] = max; } return output; }