首页 > 其他分享 >leetcode-121-easy

leetcode-121-easy

时间:2023-01-03 21:45:26浏览次数:40  
标签:maxVal min profit day 121 int easy prices leetcode

Best Time to Buy and Sell Stock

You are given an array prices where prices[i] is the price of a given stock on the ith day.

You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.

Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

Example 1:

Input: prices = [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.
Example 2:

Input: prices = [7,6,4,3,1]
Output: 0
Explanation: In this case, no transactions are done and the max profit = 0.
Constraints:

1 <= prices.length <= 105
0 <= prices[i] <= 104

思路一:最开始想到的是最简单的解法,双层循环,遍历所有可能性,但是超时了。后来想想,维护两个值,一个是当前最优解,一个是当前最小的值,每次遍历下一个数字的时候,更新这个两个值,就能求解。评论区有个解释很好

动态规划 前i天的最大收益 = max{前i-1天的最大收益,第i天的价格-前i-1天中的最小价格}
public int maxProfit(int[] prices) {
    if (prices.length < 2) return 0;

    int maxVal = prices[0] < prices[1] ? prices[1] - prices[0] : 0;
    int min = Math.min(prices[0], prices[1]);

    for (int i = 2; i < prices.length; i++) {
        if (prices[i] < min) {
            min = prices[i];
        } else {
            maxVal = Math.max(prices[i] - min, maxVal);
        }
    }

    return maxVal;
}

标签:maxVal,min,profit,day,121,int,easy,prices,leetcode
From: https://www.cnblogs.com/iyiluo/p/17023456.html

相关文章

  • leetcode-441-easy
    ArrangingCoinsYouhavencoinsandyouwanttobuildastaircasewiththesecoins.Thestaircaseconsistsofkrowswheretheithrowhasexactlyicoins.Th......
  • leetcode-459-easy
    RepeatedSubstringPatternGivenastrings,checkifitcanbeconstructedbytakingasubstringofitandappendingmultiplecopiesofthesubstringtogether......
  • leetcode-492-easy
    ConstructtheRectangleAwebdeveloperneedstoknowhowtodesignawebpage'ssize.So,givenaspecificrectangularwebpage’sarea,yourjobbynowisto......
  • leetcode-144-easy
    BinaryTreePreorderTraversalGiventherootofabinarytree,returnthepreordertraversalofitsnodes'values.Example1:Input:root=[1,null,2,3]Out......
  • [Leetcode Weekly Contest]326
    链接:LeetCode[Leetcode]2520.统计能整除数字的位数给你一个整数num,返回num中能整除num的数位的数目。如果满足nums%val==0,则认为整数val可以整除nums......
  • 【队列】LeetCode 232. 用栈实现队列
    题目链接232.用栈实现队列思路设置一个主栈mainStack和一个辅助栈assistantStack,在进行入队的时候,将mainStack中的元素全部放入assistantStack中,再将x入队,然......
  • [LeetCode] 1325. Delete Leaves With a Given Value 删除给定值的叶子结点
    Givenabinarytree root andaninteger target,deleteallthe leafnodes withvalue target.Notethatonceyoudeletealeafnodewithvalue target, ......
  • 【队列】LeetCode 225. 用队列实现栈
    题目链接225.用队列实现栈思路设置一个主队列mainQueue和一个辅助队列assistantQueue,在进行压栈的时候,将mainQueue中的元素全部放入assistantQueue中,再将x压......
  • Leetcode[LeetCode]4 两个有序数组的中位数
    上图为剑指Offer之字符串的排列,基于回溯法的思想。简单算法01数组中第二大的数02合并排序链表03链表反转04判断链表环05两个链表的首个交点06数组中出现大与一般的数07手写......
  • 【链表】LeetCode 328. 奇偶链表
    题目链接328.奇偶链表思路根据题意,我们只需要将扫描到的索引为奇数的结点不断插入到正确位置。比如1->2->3->4->5==》1->3->2->4->5==》1->3->5->2->4在扫描过......